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.
Kongruensligninger
Moderatorer: Vektormannen, espen180, Aleks855, Solar Plexsus, Gustav, Nebuchadnezzar, Janhaa
-
- Euler
- Innlegg: 5889
- Registrert: 26/09-2007 19:35
- Sted: Trondheim
- Kontakt:
Elektronikk @ NTNU | nesizer
Alt som ikke er et multippel av modulusen, riktignok. I.e. gcd(a,p)=1, hvorVektormannen skrev: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.
[tex]a^{p-1} \equiv 1 (mod p)[/tex].
M.Sc. Matematikk fra NTNU.
-
- Euler
- Innlegg: 5889
- Registrert: 26/09-2007 19:35
- Sted: Trondheim
- Kontakt:
Det er en viktig presisjon.
Elektronikk @ NTNU | nesizer