Hitta rest av ett tal med stor exponent? (Modulo)

Hej, har en uppgift i sommarmatte som lyder såhär,

Bestäm resten då 5^111 delas med 8.


Här är hur jag har tänkt, jag började efter att kolla efter mönster i rester. Men behövde komplettera mitt svar. Finns det kanske ett enklare sätt att göra denna uppgiften på?

Tacksam för all hjälp.

Det går att göra enklare. I uttryck med additioner och multiplikationer kan man byta ut kongruenta tal och få ett tal som är kongruent med det tidigare.

5¹¹¹=5^(2*55+1)=(5²)⁵⁵*5=25⁵⁵*5

25 kan nu ersättas med ett kongruent tal.

Lyckas inte räkna rätt, är det någon här som kan?

Bestäm resten då 2^38 delas med 5. Och hur tusan förklarar man vad det är man gör?

utnyttja att a^(p-1)=1 (mod p) , p ett primtal

Hajjar inte..antar att det är 5 som är primtalet.

2^(5-1)..vart leder det för att lösa 2^38 div 5?

Försök att skriva om 2^38 till något som innehåller ett tal som är kongruent med 1 eller -1 modulo 5.

så här: 38 = (4*9) + 2 så du har 2^(4*9 +2) = (2^(4))^9 * 2^2

Får det till att:

16^9 * 2^2 ==(mod 5) 3^9 * 4

Men det bör väl utvecklas?

Modulo 5 gäller 16 ~ 1 eftersom 16 = 3 * 5 + 1. Du har tagit heltalskvoten 3 i stället för resten 1.

Detta ger
2^38 = (2^4)^9 * 2^2 = 16^9 * 4 ~ 1^9 * (-1) = -1 ~ 4.

Alltså gäller 2^38 ~ 4 modulo 5.

En kontroll av det faktiska värdet visar att vi har gjort rätt:
2^38 = 274877906944
Sista (högraste) siffran är 4 så resten vid division med 5 blir också 4.

Har jag förstått rätt?

38=(4*9)+2
2^(4*9+2) = ((2^4)^9) * 2^2
16^9 * 4 ==(mod 5) 1^9 * (-1)
-1==(mod 5) 4

2^38 ==(mod5) 4

Korrekt. Det är dock litet svårt att bedöma om du verkligen har förstått varför kongruenserna gäller.

Tack för all hjälp!

Jag förstår helheten, och vad man är ute eftter, men inte hur man "vet" att:
16^9 * 4 är kongruent (mod 5) med 1^9 * (-1)