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