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.

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

Innlegg Mattebruker » 08/07-2020 20:22

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

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

Innlegg Janhaa » 09/07-2020 13:01

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]
Janhaa offline
Boltzmann
Boltzmann
Brukerens avatar
Innlegg: 8388
Registrert: 21/08-2006 02:46
Bosted: Grenland

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

Innlegg Mattebruker » 09/07-2020 17:56

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 )
Mattebruker offline

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

Innlegg Janhaa » 10/07-2020 11:36

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]
Janhaa offline
Boltzmann
Boltzmann
Brukerens avatar
Innlegg: 8388
Registrert: 21/08-2006 02:46
Bosted: Grenland

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

Innlegg Mattebruker » 10/07-2020 18:01

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 offline

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

Innlegg Mattebruker » 12/07-2020 15:04

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 )
Mattebruker offline

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

Innlegg Aleks855 » 12/07-2020 17:48

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
Aleks855 offline
Rasch
Rasch
Innlegg: 6568
Registrert: 19/03-2011 15:19
Bosted: Trondheim

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

Innlegg Mattebruker » 12/07-2020 20:11

Korrekt ! Har du ein oppfølgar ?
Mattebruker offline

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

Innlegg Aleks855 » 12/07-2020 20:35

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
Aleks855 offline
Rasch
Rasch
Innlegg: 6568
Registrert: 19/03-2011 15:19
Bosted: Trondheim

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

Innlegg veien via modulo 29 » 13/07-2020 00:39

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

Hvem er i forumet

Brukere som leser i dette forumet: Google [Bot] og 6 gjester

cron