Welchen Rest lässt 25^64 bei Division durch 9?

Question

Aufgabe:

Welchen Rest lässt 25⁶⁴ bei Division durch 9?

Problem/Ansatz:

25 : 9 = 2*9 + 7

25⁶⁴ ≡ 7⁶⁴ (mod 9)

25 ≡ 7 (mod 9)

Hier komme ich jetzt nicht weiter. Kann mir jemand von euch helfen bitte?

Answer 1

Die prime Restklassengruppe mod 9 hat die Ordnung 6. Daher:

\(25^{64}\equiv (-2)^{60+4}\equiv ((-2)^6)^{10}(-2)^4\equiv\) Kleiner Fermat:

\(1^{10}(-2)^4=16\equiv 7\) mod \(9\).

Answer 2

25^64 
≡ 7^64 
≡ (-2)^64 
≡ ((-2)^6)^10 * (-2)^4
≡ 64^10 * 16
≡ 1^10 * 16 
≡ 1 * 7
≡ 7 (MOD 9)