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.
