Eulers teorem - eit vidunderverktøy ?
Lagt inn: 22/03-2023 09:44
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.
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.