Primitive root modulo prime power

Question

If I find $a$ is PR mod p, then a theorem states that either $a$ itself or $a+p$ is the PR mod $p^2$. Is there a fast approach to check the exponents of $a$, instead of going through every element in $\{1,...,\phi(p^2)\}$? I recall that the exponent of $a$ ($ord_{p^2}(a)$) takes value in the set all the divisors of $\phi(p^2)$, but I am not sure if I remember it correctly.

More over since modulo $p^2$ extends from modulo $p$, I wonder if $\phi(p)$ is going to involve in the exponent $e$ of $a^e \equiv 1$ mod $p^2$? Thanks in advance!

---

A concrete example: 2 is found to be a primitive root modulo 13, how can I show 2 is also a root mod $13^2$? For exponent of 2, am I going to check all the divisors of $\phi(13^2)$= 156: $\{1, 2, 3, 4, 6, 12, 13, 26, 39, 52, 78, 156\}$, and show 156 itself is the least $e$ such that $2^e\equiv 1$ mod $13^2$?

---

A relevant, and more general result: (https://en.wikipedia.org/wiki/Primitive_root_modulo_n)

Answer 1

Suppose that $a$ is a primitive root (mod $p$). A more precise result is:

• $a$ is a primitive root (mod $p^2$) if and only if $a^{p-1}\not\equiv1$ (mod $p^2$);
• of the $p$ numbers $a$, $a+p$, ..., $a+(p-1)p$, exactly one of them satisfies $(a+kp)^{p-1}\equiv 1$ (mod $p^2$).

So you can simply compute $a^{p-1}$ modulo $p^2$ to determine the answer.