Berechnen Sie 6475 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.