Kongruensligninger

[Vektormannen]

Her må man rett og slett prøve seg litt frem. Først bør man prøve å redusere grunntallet i potensen mest mulig, til 22 i dette tilfellet. Deretter må man se hva man kan gjøre videre. Det kan være lurt å skrible ned noen av tingene man vet. For eksempel vet vi at siden 101 er et primtall så er [tex]a^{100} \equiv 1[/tex] fra Fermats lille teorem. Det betyr at alt som er opphøyd i et multippel av 100 vil være kongruent med 1, og det er noe vi får bruk for.

Når jeg ser på det nå så ville det vært enklere å bare si at [tex]123^{1002} \equiv 22^{1002} \equiv 22^{1000} \cdot 22^2 \equiv 1 \cdot 22^2 \equiv -21[/tex]. Som vi ser er det mange veier i mål.

[wingeer]

Her må man rett og slett prøve seg litt frem. Først bør man prøve å redusere grunntallet i potensen mest mulig, til 22 i dette tilfellet. Deretter må man se hva man kan gjøre videre. Det kan være lurt å skrible ned noen av tingene man vet. For eksempel vet vi at siden 101 er et primtall så er [tex]a^{100} \equiv 1[/tex] fra Fermats lille teorem. Det betyr at alt som er opphøyd i et multippel av 100 vil være kongruent med 1, og det er noe vi får bruk for.

Når jeg ser på det nå så ville det vært enklere å bare si at [tex]123^{1002} \equiv 22^{1002} \equiv 22^{1000} \cdot 22^2 \equiv 1 \cdot 22^2 \equiv -21[/tex]. Som vi ser er det mange veier i mål.

Alt som ikke er et multippel av modulusen, riktignok. I.e. gcd(a,p)=1, hvor
[tex]a^{p-1} \equiv 1 (mod p)[/tex].

[Vektormannen]

Det er en viktig presisjon.