Moduloräkning

Hej!
Snälla nån som jag hjälpa mig med min uppgift?
Bestäm resten då 4 ^40 delas med 7 .

Vi börjar med att betrakta restklasserna då en potens av 4 divideras med 7:

4^1 mod 7 = 4
4^2 mod 7 = 16 mod 7 = 3
4^3 mod 7 = 64 mod 7 = 1 (7*9 =63)

Alltså har vi att 4^3 är kongruent 1 mod 7. Av detta får vi att vi kan skriva om uttrycket:
(hittar ingen rimlig funktion så antag att == uttrycker kongruens)

4^40 mod 7 == (1)^(3*13) * 4^1 mod 7 == 1 *4 mod 7 == 4

Alltså: 4^40 mod 7 är kongruent med 4.

4^40=2^80
2^6==1 mod 7 (fermat lilla sats eller så kan du att 2^6=64, bra kunna 2 potenser)
2^80=(2^6)^13 *2^2==4 mod 7

16==2 mod 7 och inte 3

Ah, helt rätt. Hade såklart ingen betydelse för denna uträkningen, men du har såklart helt rätt.

Har en liknande uppgift som jag inte har lyckats lösa.

Jag har 2^29 som ska divideras med 9 där resten ska bestämmas.

Är det någon som skulle kunna hjälpa mig lite?

2^3 = 8 = 9-1 ~ -1 (mod 9)