Berechnen Sie mit Chinesischem Restsatz 2413 mod 225

Question

Aufgabe:

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

2⁴¹³ 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² * 5²

Und Phi(5³) = 5² * 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 ...