Kongruensproblem

[moth]

Oppgaven er: Finn resten når vi dividerer 53[sup]12[/sup] med 17.

[tex]53\equiv2\;(mod\;17)[/tex]
[tex]53^{12}\equiv2^{12}\;(mod\;17)[/tex]

[tex]2^6\equiv13\;(mod\;17)[/tex]
[tex]2^{12}\equiv169\;(mod\;17)[/tex]

[tex]169\equiv16\;(mod\;17)[/tex]

[tex]53^{12}\equiv16\;(mod\;17)[/tex]

Så resten er 16, men finnes det en enklere måte å finne det litt mer direkte? Så jeg slipper å gå gjennom alle stegene?

[Charlatan]

Siden 17 er et primtall, så vet du at [tex]53^{16}=1[/tex] av fermats lille sats, så det vil si at [tex]53^{12}=53^{-4}=(53^{-1})^4[/tex] som er enklere å regne ut etter du har funnet inversen til 53.

[moth]

Hmm, vet ikke helt om jeg skjønte det egentlig. Er ikke så godt kjent med Fermat's lille teorem, men jeg skal se på det litt seinere. Men dette kan vel kun brukes når det er et primtall? Jeg tenkte mer på generelle metoder som kan brukes alltid.

[Charlatan]

Noe som kalles eulers teorem, en mer generell versjon av fermats lille sats, sier at [tex]a^{\phi(n)} = 1 \pmod{n}[/tex] hvis og bare hvis [tex]\gcd(a,n) = 1[/tex], der [tex]\phi(n)[/tex] er antall tall under n som er relativt primske med n.

Dette kan du bruke til å forkorte på potensene på samme måte.

Hvis tallet ditt ikke er relativt primsk med n, så kan du faktorisere ut den delen som er det, og dermed bruke metoden på denne faktoren.

[Charlatan]

Det over krever selvsagt litt teori utenom videregåendepensum. Hvis ikke kan jeg ikke øyeblikkelig se noen enklere måte å redusere slike uttrykk på. Du kommer likevel langt med forskjellige snedige observasjoner av samme type du har gjort.

[moth]

Ja det er nok litt over mitt nivå dette, men jeg skal se på det litt nøyere og kanskje jeg kan forstå noe. Takk for hjelpen ihvertfall!