Primitive Root Modulo Prime Power

Question

Wenn ich ... finde $a$ ist PR mod p, dann besagt ein Theorem, dass entweder $a$ selbst oder $a+p$ ist der PR mod $p^2$. Gibt es einen schnellen Ansatz, um die Exponenten von zu überprüfen$a$, anstatt jedes Element in durchzugehen $\{1,...,\phi(p^2)\}$? Ich erinnere mich, dass der Exponent von$a$ ($ord_{p^2}(a)$) nimmt in der Menge alle Teiler von Wert an $\phi(p^2)$, aber ich bin mir nicht sicher, ob ich mich richtig daran erinnere.

Mehr seit Modulo $p^2$ erstreckt sich von Modulo $p$, Ich frage mich, ob $\phi(p)$ wird in den Exponenten involviert sein $e$ von $a^e \equiv 1$ mod $p^2$? Danke im Voraus!

---

Ein konkretes Beispiel: 2 ist ein primitives Root-Modulo 13. Wie kann ich zeigen, dass 2 auch ein Root-Mod ist? $13^2$? Für den Exponenten 2 werde ich alle Teiler von überprüfen$\phi(13^2)$= 156: $\{1, 2, 3, 4, 6, 12, 13, 26, 39, 52, 78, 156\}$und Show 156 selbst ist die geringste $e$ so dass $2^e\equiv 1$ mod $13^2$?

---

Ein relevantes und allgemeinere Ergebnis:

(https://en.wikipedia.org/wiki/Primitive_root_modulo_n)

Answer 1

Nehme an, dass $a$ ist eine primitive Wurzel (mod $p$). Ein genaueres Ergebnis ist:

• $a$ ist eine primitive Wurzel (mod $p^2$) dann und nur dann, wenn $a^{p-1}\not\equiv1$ (mod $p^2$);
• des $p$ Zahlen $a$, $a+p$, ..., $a+(p-1)p$, genau einer von ihnen befriedigt $(a+kp)^{p-1}\equiv 1$ (mod $p^2$).

Sie können also einfach rechnen $a^{p-1}$ Modulo $p^2$ um die Antwort zu bestimmen.