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.
