Kongruensräkning
Frågan är: Bestäm resten då 5^133 delas med 7
Mitt svar som jag har kommit fram är :
Jag börjar och undersöka alla potenser av 5 och se vilka är kongruenta med mod 7. Detta gör jag för att alla tal dividerat med 5 som är kongruenta mod 7 får samma rest. Jag vill alltså hitta någon potens kongruent med 1 eller 6 (dvs -1). Detta innebär att 5 upphöjd till någon tal får resten 1 eller 6 vid mod 7.
(5^6) ger resten 1 vid mod 7. så jag skriver om beräkningen 5^(6*22+1).
Vi kan byta ut kongruenta tal mot varandra här för att de ger samma rest. 5* 1^22=5 .
5=5 (mod 7) Resten är alltså 5.
Resten måste vara ett positiv heltal mindre än 7 vilket som stämmer med det jag har fått.
Men min fråga är att hur vet jag att jag har funnit resten?
Hur kan jag reda på om jag har kommit fram till rätt svar?
Om metoden är rätt och räkningarna är rätt så är svaret rätt och det verkar ju vara uppfyllt här.
Annars är ju en möjlighet att lösa det ekvivalenta (-2)^133 mod7
men inte ens här är det praktiskt att räkna ut potensen ( som har ca 40 siffror) och utföra divisionen...
Om du har digitala verktyg i närheten och får använda dem så gör det. T. ex. Python kan räkna ut svaret direkt.
Du kan kontrollera svaret med wolframalpha:
https://www.wolframalpha.com/input/?i=5%5E133mod7
