Radice primitiva modulo potere primo

Question

Se trovo $a$ è PR mod p, quindi un teorema lo afferma $a$ stesso o $a+p$ è il PR mod $p^2$. Esiste un approccio rapido per controllare gli esponenti di$a$, invece di esaminare ogni elemento in $\{1,...,\phi(p^2)\}$? Ricordo che l'esponente di$a$ ($ord_{p^2}(a)$) assume valore nell'insieme tutti i divisori di $\phi(p^2)$, ma non sono sicuro di ricordarlo correttamente.

Più oltre dal modulo $p^2$ si estende da modulo $p$, Mi chiedo se $\phi(p)$ sta per coinvolgere l'esponente $e$ di $a^e \equiv 1$ mod $p^2$? Grazie in anticipo!

---

Un esempio concreto: 2 risulta essere una radice primitiva modulo 13, come posso mostrare che 2 è anche una radice mod $13^2$? Per l'esponente 2, controllerò tutti i divisori di$\phi(13^2)$= 156: $\{1, 2, 3, 4, 6, 12, 13, 26, 39, 52, 78, 156\}$, e lo stesso spettacolo 156 è il minimo $e$ tale che $2^e\equiv 1$ mod $13^2$?

---

Un risultato rilevante e più generale:

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

Answer 1

Supporre che $a$ è una radice primitiva (mod $p$). Un risultato più preciso è:

• $a$ è una radice primitiva (mod $p^2$) se e solo se $a^{p-1}\not\equiv1$ (mod $p^2$);
• del $p$ numeri $a$, $a+p$, ..., $a+(p-1)p$, esattamente uno di loro soddisfa $(a+kp)^{p-1}\equiv 1$ (mod $p^2$).

Quindi puoi semplicemente calcolare $a^{p-1}$ modulo $p^2$ per determinare la risposta.