Bestimmen Sie drei Primitivwurzeln modulo 625

Question

Hi, wir behandeln gerade Primitivwurzeln und ich habe noch eine Frage die ich im Unterricht nicht verstanden habe:

Bestimmen Sie drei Primitivwurzeln modulo 625. Wieviele Primitivwurzeln gibt es modulo 625?

Answer 1

Im Allgemeinen hat eine zykliche Gruppe der Ordnung $m$ genau
$\varphi(m)$ Erzeuger.

Die zyklische Gruppe $(\mathbb Z/n\mathbb Z)^*$ hat Ordnung $\varphi(n)$.

Die Anzahl der Erzeuger bzw. Primitivwurzeln modulo 625 ist somit $\varphi(\varphi(625))$.

Jetzt weiß man, dass für $p$ ungerade und $x$ eine primitive Wurzel modulo $p^2$, x auch schon eine primitive Wurzel modulo höheren $p$-Potenzen ist.

Das heißt suche erst einmal eine primitive Wurzel modulo $5^2 = 25$. Nennen wir diese mal $g$, dann ist diese auch eine primitive Wurzel modulo 625, also $(\mathbb Z/625\mathbb Z)^* = \langle g \rangle$.

Damit kannst du jetzt aber schnell weitere primitive Wurzeln finden, indem du bestimmte Potenzen von $g$ betrachtest.