Rest von 5^10000 mod 99

Question

Aufgabe:

Berechnen Sie den Rest von \( 5^{10000} \) mod \( 99 \)

Problem/Ansatz:

Suche das beste schrittweise Vorgehen für diese Aufgabe.

1. Primfaktorzerlegung von \( 99 = 3^2 \cdot 11 \)

2. \( \varphi(99) = 60 \)

3. ...?

Answer 1

Satz von Euler liefert wegen ggT(5,99)=1

5^60 ≡ 1 (mod 99)

und damit auch für jedes Vielfach von 60 und damit

5^(9960)≡ 1 (mod 99)

und also

5^(10000) = 5^(9960+40)=5^(9960)*5^(40)  ≡ 5^(40) (mod 99)

Damit geht es nur noch um 5^40 ≡ x (mod 99).

Es ist 5^4 = 625 = 6*99+31

Also ist  5^40 ≡ 31^10  (mod 99)

und 31^2=961=990-29 also

31^2 ≡ -29 (mod 99)

Also  -29^5 ≡ x (mod 99)

und (-29)^2=841 ≡ 49 (mod 99)

Damit ist  -29^5 ≡ 49*49*(-29) (mod 99)

                         ≡ 25*(-29) (mod 99)

                        ≡ 67 (mod 99)

Vermutlich gibt es noch einen schnelleren Weg, aber im

Prinzip kann so immer Stück für

Stück hinabsteigen.