Potenz 7525 im Restklassenring ℤ17 berechnen

Question

ich verstehe den zweiten Schritt der Berechnung nicht.

1. Exponent in Binärform: 25 = 11001

2. Was ich nicht verstehe ist, warum die Basis 75 = 7 mod 17 ist.

17 ist der Rest aber woher kommt die 7? Wenn ich das wüsste, könnte und möchte ich die Rechnung selber fortsetzen.

Answer 1

$$75 \equiv 7 \mod 17$$da $75 = 68 + 7 = 4 \cdot 17 + 7$.

17 ist der Rest aber woher kommt die 7?

Nein - $7$ ist der Rest nach der Division durch $17$. Kommst Du allein weiter?

Gruß Werner

Comments

Ahh, ich rechne es mal aus und schreibe das Ergebnis gleich mal rein. Vielen Dank, das erklärt einiges

---

Das Ergebnis ist 10?

Könntest du es einmal vorrechnen um die Rechenwege zu vergleichen?

---

Das Ergebnis ist 10?

das ist richtig!

---

Könntest du es einmal vorrechnen um die Rechenwege zu vergleichen?

Aus $75 ^{25} \equiv x \mod 17$ wird$$7^{16 + 9} \equiv 7^9 \equiv x \mod 17$$da $\varphi(17) = 17-1=16$ siehe Satz von Euler-Fermat. Die $9$ ist binär $1001_2$. Mit der binären Exponentiation eine kleine Tabelle aufstellen$$\begin{array} {r|cc} & z & \text{Ergebnis} \\ \hline & 7 & 1 \\ \hline 1 & 7^2 \equiv 15 & 7\cdot 1 \equiv 7 \\ 0 & 15^2 \equiv 4 & 7\\ 0 & 4^2 \equiv 16 & 7\\ 1 & & 16 \cdot 7 \equiv 10 \end{array}$$in der ersten Spalten stehen die Ziffern der Binärzahl. Die kleinste Position steht oben! Wenn dort eine $1$ steht, wird in der Spalte 'Ergebnis' das Produkt der beiden Zahlen aus der Zeile vorher geschrieben. Bei $0$ bleibt die Zahl erhalten. In der zweiten Spalte wird die Zahl aus der Vorgängerzeile immer quadriert. Am Ende steht in der Ergebnisspalte das Ergebnis.