# Primitive root modulo prime power

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)

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.