Ich soll 2 hoch 100 modulo 7 ohne Taschenrechner rechnen wie mache ich das?
Da 7 und die 2 teilerfremd sind, bzw. der größte gemeinsame Teiler ggT (7, 2) = 1 ist,
erhält man sofort mit den zweier Exponenten mit
wann der Rest 1 ist.
ist die Eulersche PHI-Funktion.
(Satz von Euler)
Es sei , und ggT(a, m) = 1.
Dann ist .
Jetzt zerlegen wir den Exponenten, die 100, in ein Vielfaches von 6 und einem Rest.
Wir erhalten:
Der gesuchte Rest ist die 2
