Berechnen Sie mit Chinesischem Restsatz 2^413 mod 225

Question

Aufgabe:

Berechnen Sie mit den Algorithmen der Vorlesung (Chinesischer Restsatz) und ohne Hilfe eines Computers:

2^413 mod 225

Hinweis:

Verwenden Sie im Teil b) den Chinesischen Restsatz und den kleinen Satz von Fermat. Verwenden Sie außerdem, dass für die Eulersche Phifunktion gilt ϕ(pk) = p^k − p^k−1 für alle Primzahlen p, k ∈ N und k ≥ 1. Letztere Formel haben wir im Vorlesungsforum ebenfalls besprochen

Answer 1

Es ist \(225=5^3\) Die prime Restklassengruppe modulo 225 hat also

die Ordnung \(\phi(5^3)=5^3-5^2=200\).

Nach Fermat gilt dann \(2^{200}\equiv 1\) modulo \(225\), usw.

Diese Aussagen sind falsch. Siehe die folgenden Kommentare.

Comments

Eher 225 = 3^2 * 5^2

Und Phi(5^3) = 5^2 * 4 = 100

---

Oh sorry. Dann kann man den chinesischen Restsatz

ja doch noch verwenden ;-)

Da habe ich ja ziemlichen Murx geliefert ..

Aber nun ist \(\phi(225)=\phi(3^2)\phi(5^2)=6\cdot 20=120\),

also \(2^{120}\equiv 1\) mod \(225\), also ...