Primitive root mod $p^2$ and $p^4$

Question

If $a$ is not a primitive root mod $p^2$ for a prime $p$. What is the fastest way of checking if $a$ is (or it is not) a primitive root mod $p^4$? Is there any useful trick?

Thanks!

Answer 1

You look at it and decide it isn't a primitive root modulo $p^4$.

Assume that $a$ is not a primitive root modulo $p^r$. Then it is not a primitive root modulo $p^{r+1}$ either.

This is clear if $\gcd(a,p)=p$, so assume $\gcd(a,p) = 1$. There exists $k$, a proper divisor of $(p-1)p^{r-1}$ such that $a^k\equiv 1\pmod{p^r}$. So $a^k=1+p^r$. Then $a^{pk} = (1+p^r)^p$. But every term in the expansion of $(1+p^r)^p$, except for the first, is divisible by $p^{r+1}$, so $a^{kp}\equiv 1\pmod{p^{r+1}}$. So the order of $a$ modulo $p^{r+1}$ is a divisor of $kp$, which is a proper divisor of $(p-1)p^r$. So $a$ is not a primitive root modulo $p^{r+1}$.

In fact we have a converse, as shown here:

Theorem. Let $a$ be an integer, $p$ a prime, $\gcd(a,p)=1$. Then $a$ is a primitive root modulo $p^2$ if and only if it is a primitive root modulo $p^r$ for every $r\geq 1$.