Berechnen Sie 6^{475} mod 13 , Zwischenschritte?

Question

Aufgabe:

Berechnen Sie \( 6^{475} \bmod 13 \) .
Nach dem Satz von Fermat ist \( 6^{12} \equiv 1(\bmod 13) \). Division mit Rest liefert \( 475 \equiv 7(\bmod 13) \), also ist \( 6^{475} \equiv 6^{7}(\bmod 13) \). Jetzt rechnet man:
\( 6^{2}=36 \equiv 10, \quad 6^{4} \equiv 10^{2}=100 \equiv 9, \quad 6^{6}=6^{4} \cdot 6^{2} \equiv 9 \cdot 10 \equiv 12, \quad 6^{7}=6^{6} \cdot 6 \equiv 12 \cdot 6 \equiv 7 \quad(\bmod 13) \)

Kann mir das jemand bitte erklären? Ich verstehe die einzelnen Schritte nicht.

Verstanden habe ich das:

\( a \equiv b -> a^k \equiv b^k \)

\(a^p \equiv a mod p\)

\(a^{p-1} \equiv 1 mod p \)

Comments

Kann ich also wegen \( a^k \equiv b^k \) einfach

\( 6^2 \equiv 10 \) zu \( 6^4 \equiv 10^2 \) machen?

also quasi: \( (6^2)^2 \equiv (10)^2 \)

---

Kann ich also wegen \( a^k \equiv b^k \) einfach\( 6^2 \equiv 10 \) zu \( 6^4 \equiv 10^2 \) machen?

Ja - und wenn man das ein wenig systematisiert, gibt das die hier beschriebene Tabelle. In Deine Fall sähe es so aus:$$\begin{array}{}a_i& b_i& c_i\\\hline 6& 7& 1\\ 10& 3& 6\\ 9& 1& 8\\ 3& 0& 7\end{array}$$Es gilt immer \(a_i^{b_i} \cdot c_i \equiv 6^{7} \mod 13\) in jeder \(i\)'ten Zeile.

Answer 1

Kann ich also wegen \( a^k \equiv b^k \) einfach\( 6^2 \equiv 10 \) zu \( 6^4 \equiv 10^2 \) machen?also quasi: \( (6^2)^2 \equiv (10)^2 \)

Ja, genau das passiert da. Die Potenzgesetze gelten auch in der Modul-Rechnung. Es wird nur bei Zwischenschritten immer modulo gerechnet, um die Zahlen klein zu halten. Damit muss man dann keine großen Potenzen berechnen können, wie du an deinem Beispiel gut sehen kannst.