Poder principal do módulo da raiz primitiva

Question

Se eu encontrar $a$ é PR mod p, então um teorema afirma que qualquer um $a$ em si ou $a+p$ é o mod PR $p^2$. Existe uma abordagem rápida para verificar os expoentes de$a$, em vez de passar por cada elemento em $\{1,...,\phi(p^2)\}$? Eu me lembro que o expoente de$a$ ($ord_{p^2}(a)$) assume valor no conjunto de todos os divisores de $\phi(p^2)$, mas não tenho certeza se me lembro bem.

Mais desde o módulo $p^2$ estende-se do módulo $p$, Eu me pergunto se $\phi(p)$ vai envolver no expoente $e$ do $a^e \equiv 1$ mod $p^2$? Desde já, obrigado!

---

Um exemplo concreto: 2 é considerado um módulo de raiz primitiva 13, como posso mostrar que 2 também é um mod de raiz $13^2$? Para expoente de 2, vou verificar todos os divisores de$\phi(13^2)$= 156: $\{1, 2, 3, 4, 6, 12, 13, 26, 39, 52, 78, 156\}$, e mostrar o próprio 156 é o mínimo $e$ de tal modo que $2^e\equiv 1$ mod $13^2$?

---

Um resultado relevante e mais geral:

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

Answer 1

Suponha que $a$ é uma raiz primitiva (mod $p$) Um resultado mais preciso é:

• $a$ é uma raiz primitiva (mod $p^2$) se e apenas se $a^{p-1}\not\equiv1$ (mod $p^2$);
• do $p$ números $a$, $a+p$, ..., $a+(p-1)p$, exatamente um deles satisfaz $(a+kp)^{p-1}\equiv 1$ (mod $p^2$)

Então você pode simplesmente calcular $a^{p-1}$ modulo $p^2$ para determinar a resposta.