Potenz 75^25 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.