matematikk.net

I) Fermat-Euler's teorem : a[tex]^{p-1}[/tex] [tex]\equiv[/tex] 1 ( mod p ) , der a [tex]\in[/tex] N[tex]\wedge[/tex] p = primtal


II) Euler's [tex]\varphi[/tex]- funksjon : a[tex]^{\varphi( n ) }[/tex] [tex]\equiv[/tex] 1 ( mod n ) , der gcd( a , n ) = 1

Oppgave 1 : Vis at I er eit spesialtilfelle av II.

Oppgave 2 : Vis at 1000001 [tex]\cdot[/tex] 999999 er deleleg med 13.

2)
[tex]1000001=101*9901[/tex]
og
[tex]999999=3^3*7*11*13*37[/tex]
der f eks:

[tex]3^3 \equiv 14 \pmod{13}[/tex]
og
[tex]13 \equiv 0 \pmod{13}[/tex]
ergo:
[tex]1000001*999999 \equiv 0 \pmod{13}[/tex]

dog uten Euler's phi function or FLT.

Alternativ løysing:

1000001 = 10[tex]^{6}[/tex] +1

999999 = 10[tex]^{6}[/tex] - 1

1000001 [tex]\cdot[/tex] 999999 = ( 10[tex]^{6}[/tex] + 1 )( 10[tex]^{6}[/tex] - 1 ) [ konjugatsetninga ] = 10[tex]^{12}[/tex] - 1 [ 12 = [tex]\varphi[/tex]( 13 ) ] = 10[tex]^{\varphi (13)}[/tex] - 1 [tex]\equiv[/tex] 0 ( mod 13 ) ( jamfør Euler's phi-funksjon )

Mattegjest skrev:I) Fermat-Euler's teorem : a[tex]^{p-1}[/tex] [tex]\equiv[/tex] 1 ( mod p ) , der a [tex]\in[/tex] N[tex]\wedge[/tex] p = primtal


II) Euler's [tex]\varphi[/tex]- funksjon : a[tex]^{\varphi( n ) }[/tex] [tex]\equiv[/tex] 1 ( mod n ) , der gcd( a , n ) = 1

Oppgave 1 : Vis at I er eit spesialtilfelle av II

Hvis p er et primtall, så er:

[tex]a^{\phi(n)}\equiv 1\pmod{n}[/tex]

[tex]\phi(p) = p-1[/tex]
altså:

[tex]a^{\phi(p)}\equiv 1\pmod{p}\\ \\ a^{p-1}\equiv 1\pmod{p}\\ \\ a^{p}\equiv a\pmod{p}\\[/tex]

Sjølvsagt heilt korrekt !

Meiner at Euler's teorem " parkerer " " Fermat's lille " . Sistnemnde fortener likevel sin plass i faglitteraturen ettersom den i si tid ganske sikkert blei sett på som ei betydeleg " nyvinning " innafor talteorien.

Oppfølgar:

Finn resten( remainder ) når 4444[tex]^{4444}[/tex] delast på 9.

Hint: 2[tex]^{3}[/tex] [tex]\equiv[/tex] -1 ( mod 9 )

Jeg er permanent rusten på mod-aritmetikk, men gitt tittelen på tråden, så kan vi vel bruke Eulers teorem.

$$4444^{4444} = 4444^{4+740\cdot6} \equiv 4444^4 \equiv 7^4 \equiv 7 \pmod 9$$

Håper det stemmer.

Korrekt ! Har du ein oppfølgar ?

Hmm, den er kanskje bare tangentielt relatert, men jeg syntes den var fin.

Finn alle heltall $n$ slik at $n^7 - 77$ er et Fibonacci-tall.

Aleks855 skrev:Hmm, den er kanskje bare tangentielt relatert, men jeg syntes den var fin.

Finn alle heltall $n$ slik at $n^7 - 77$ er et Fibonacci-tall.

ingen løsning mulig