Eulers teorem - eit vidunderverktøy ?

Det er god trening å prate matematikk. Her er det fritt fram for alle. Obs: Ikke spør om hjelp til oppgaver i dette underforumet.

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

Svar
Mattebruker
Weierstrass
Weierstrass
Innlegg: 456
Registrert: 26/02-2021 21:28

Denne teksten er henta frå ei lærebok i talteori:

Eulers teorem er en generalisering av Fermats teorem, og gjør bruk av Eulers [tex]\varphi[/tex]-funksjon, som er definert slik:

φ(n) er alle tall < n som er relativt primiske til n, dvs. alle tall som ikke deler noen felles faktorer med n. Det er da enkelt å se at φ(p) = 1 for alle primtall p. Vi kan
da skrive ned Eulers teorem, som gjelder for alle positive heltall a og n som ikke har noen felles faktorer (er relativt primiske):

a[tex]^{\varphi (n)}[/tex] [tex]\equiv[/tex] 1 ( mod n )

Dette er enda mer anvendelig enn Fermats lille. Vi kan f.eks. løse dette:

Spørsmål: Hva er det siste sifferet i 7[tex]^{2009}[/tex] ?

Svar: 7 og 10 er relativt primiske, så vi kan bruke Eulers teorem. φ(10) = 4, og 7[tex]^{2009}[/tex] = (7[tex]^{4}[/tex] )[tex]^{502}[/tex] [tex]\cdot[/tex] 7 [tex]\equiv[/tex] 1[tex]^{502}[/tex][tex]\cdot[/tex] 7 [tex]\equiv[/tex] 7 ( mod 10 )

Altså veit vi at divisjon med 10 gir 7 som rest , dvs. siste sifferet er 7.

Oppgaveforfattaren avsluttar dette rekneeksemplet med følgjande påstand( sitat ): Prøv å løse dette problemet uten å kunne Eulers teorem, og du vil få litt hodebry .

Innsendar meiner at denne påstanden er ei overdriving som tillegg Eulers teorem større betydning enn det fortener.

Kjem relativt lett fram til same svaret ved å bruke elementær kongruensrekning:

7 [tex]\equiv[/tex] ( - 3 ) [tex]\Rightarrow[/tex] 7[tex]^{2}[/tex] [tex]\equiv[/tex]( -3 )[tex]^{2}[/tex] [tex]\equiv[/tex] 9 [tex]\equiv[/tex] ( - 1 ) ( mod 10 ) ... o.s.v.....

Ønsker gjerne innspel frå deg som måtte lese dette innlegget.
Gustav
Tyrann
Tyrann
Innlegg: 4555
Registrert: 12/12-2008 12:44

Mattebruker skrev: 22/03-2023 09:44 Hva er det siste sifferet i 7[tex]^{2009}[/tex] ?
Ganske enig i at akkurat dette kan løses enkelt uten Euler. Det betyr ikke at Eulers teorem er noe mindre nyttig i andre tilfeller...

Forslag til løsning: $7^{2009}=7\cdot 49^{1004}\equiv 7\cdot (-1)^{1004}\equiv 7\pmod{10}$.
Mattebruker
Weierstrass
Weierstrass
Innlegg: 456
Registrert: 26/02-2021 21:28

Takk for kommentar !
Svar