Modulo mit Primzahl als Exponent

Question

Aufgabe:

5²³ mod 55

Problem/Ansatz:

Ich weiss nicht, wie ich mit der Primzahl als Exponent umzugehen habe.

Answer 1

x = 5²³ mod 55 bedeutet ja  : Es gibt ein k mit x = 5²³ + k*55

Das x ist also durch 5 teilbar und es gibt ein z mit z = 5²²+ k*11

Nach dem Satz von Fermat-Euler gilt 5¹⁰ = 1 mod 11

wegen 5²² = 5¹⁰ * 5¹⁰ * 25 ist also  5²² = 25 mod 11

bzw .   5²² = 3 mod 11. Damit ist das z=3 und es folgt x=15.

Comments

Vielen Dank für die Erklärung.

Zeile drei und vier konnte ich nachvollziehen. Jedoch habe ich noch einen Knopf, was die übrigen Zeilen betrifft. Auch was k, x und z anbelangt.

---

5²² = 25 mod 11   ==>  5²² = 3 mod 11.

Weil 25=3+2*11 also 25=3 mod 11.

Und das z ist einfach nur x:5.