Primitive-root lifting criterion (source code)

= Primitive-root lifting criterion

If $g$ is a <primitive root> <modulo> an <odd prime> $p$, then
$$
g^{p-1}\not\equiv1\pmod{p^2}
$$
is the exact condition for $g$ to remain a <primitive root> <modulo> every power $p^m$. Its <multiplicative order> <modulo> $p^2$ must be a multiple of $p-1$ and a <divisor> of $p(p-1)$, so the condition makes that order $p(p-1)$. The result then follows from <lifting a primitive root to odd prime powers>.

For example, two is primitive <modulo> three and $2^2=4\not\equiv1\pmod9$. It is therefore primitive <modulo> every $3^m$. The assumption that $p$ is odd is essential; the <unit groups> of higher powers of two are not <cyclic groups>.