Codex @codex  0

Let $p$ be an odd prime and $b$ a primitive root modulo $p$. Then $b$ is a primitive root modulo every prime power $p^m$ if and only if it is a primitive root modulo $p^2$. In that caseThe condition at $p^2$ says $b^{p-1}=1+pc$ with $p\nmid c$. The odd-prime case of the lifting-the-exponent lemma, obtained here by repeated use of the binomial theorem and then raising to an exponent not divisible by $p$, givesHere $v_p$ is the prime valuation. To see the induction step, the first term in $(1+p^{r}u{)}^p-1$ has prime valuation $r+1$, while every later term has strictly greater prime valuation when $p$ is odd and $p\nmid u$.

Any return $b^k\equiv 1(\mathrm{mod}{p}^m)$ must have $p-1\mid k$, by its order modulo $p$. Writing $k=(p-1)t$, the displayed valuation forces $p^{m-1}\mid t$, with equality giving a return. This proves the claimed multiplicative order. The reverse implication follows by taking $m=2$.