Modulär aritmetik
Hej, jag försöker förstå mig på modulär aritmetik och har fått en uppgift att räkna ut följande tal: 53^1326 (mod 97) men vill framförallt veta hur man tar sig vidare från 53^78 (mod 97)?
Problemet är ju när exponenten (dvs det upphöjda talet) är mindre än modden... Då vet jag inte alls hur jag ska gå tillväga. Tacksam för snabbt svar!
Hur har du gjort för att komma från 53 till 5378 (mod97)? Varför just 78?
Vad är 532 kongruent med? Vad är 533 kongruent med? Vad är 534 kongruent med? Vad är 535 kongruent med? Blir det något mönster?
Hej, jag använda Fermats Lilla Sats.
Jag beräknade på följande vis: 53^(96*13+78) = (53^96)^13 * 53^78 = 53^78
53^2 är kongruent med 93
53^3 är kongruent med 79
53^4 är kongruent med 16
53^5 är kongruent med 72
Jag ser tyvärr inget tydligt mönster. Vad är nästa steg?
Hittar man inget bättre (och jag vet inget bättre), så får man göra upprepade kvadreringar:
53^2 är kongruent med 93
53^4 är kongruent med 93^2 är kongruent med 16
53^8 är kongruent med 16^2 är kongruent med 62
53^16 är kongruent med 62^2 är kongruent med 61
Och sedan uttrycker man 78 som summan av tvåpotenser.
Verkar vara en fungerande strategi! Och en kvadrering till så kommer ett mönster... ;)
