Euler's [tex]\varphi[/tex]-funksjon

Her kan brukere av forum utfordre hverandre med morsomme oppgaver og nøtter man ønsker å dele med andre. Dette er altså ikke et sted for desperate skrik om hjelp, de kan man poste i de andre forumene, men et sted for problemløsing på tvers av trinn og fag.

Moderatorer: Vektormannen, espen180, Aleks855, Solar Plexsus, Gustav, Nebuchadnezzar, Janhaa

Svar
Mattebruker

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.
Janhaa
Boltzmann
Boltzmann
Innlegg: 8552
Registrert: 21/08-2006 03:46
Sted: Grenland

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.
La verken mennesker eller hendelser ta livsmotet fra deg.
Marie Curie, kjemiker og fysiker.

[tex]\large\dot \rho = -\frac{i}{\hbar}[H,\rho][/tex]
Mattebruker

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 )
Janhaa
Boltzmann
Boltzmann
Innlegg: 8552
Registrert: 21/08-2006 03:46
Sted: Grenland

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]
La verken mennesker eller hendelser ta livsmotet fra deg.
Marie Curie, kjemiker og fysiker.

[tex]\large\dot \rho = -\frac{i}{\hbar}[H,\rho][/tex]
Mattebruker

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.
Mattebruker

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 )
Aleks855
Rasch
Rasch
Innlegg: 6855
Registrert: 19/03-2011 15:19
Sted: Trondheim
Kontakt:

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.
Bilde
Mattebruker

Korrekt ! Har du ein oppfølgar ?
Aleks855
Rasch
Rasch
Innlegg: 6855
Registrert: 19/03-2011 15:19
Sted: Trondheim
Kontakt:

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.
Bilde
veien via modulo 29

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
Svar