Ich soll 2 hoch 100 modulo 7 ohne Taschenrechner rechnen wie mache ich das?
\(\begin{array}{rcll} 2^{100}\pmod 7 \end{array}\)
Da 7 und die 2 teilerfremd sind, bzw. der größte gemeinsame Teiler ggT (7, 2) = 1 ist,
erhält man sofort mit \(\varphi(7) = 6 \) den zweier Exponenten mit \( 2^6 \equiv 1 \pmod 7.\)
wann der Rest 1 ist.
\(\varphi{(n)}\) ist die Eulersche PHI-Funktion.
(Satz von Euler)
Es sei \(m \in N\), \(a \in Z\) und ggT(a, m) = 1.
Dann ist \(a^{\varphi(m)} \equiv 1 \pmod m\).
Jetzt zerlegen wir den Exponenten, die 100, in ein Vielfaches von 6 und einem Rest.
\(100 = 6\cdot 16 + 4\)
Wir erhalten:
\(\begin{array}{rcll} 2^{6\cdot16 + 4}\pmod 7 \\ \equiv & 2^{6\cdot16}\cdot 2^{4}\pmod 7 \\ \equiv & (\underbrace{2^{6}}_{=1})^{16}\cdot 2^{4}\pmod 7 \qquad & | \qquad 2^6 \equiv 1 \pmod 7\\ \equiv & (1)^{16}\cdot 2^{4}\pmod 7 \qquad & | \qquad 1^{16} = 1 \\ \equiv & 1\cdot 2^{4}\pmod 7 \\ \equiv & 2^{4}\pmod 7 \\ \equiv & 16 \pmod 7 \\ \equiv & 2 \pmod 7 \\ \end{array}\)
Der gesuchte Rest ist die 2
+14538 
!
