# How to prove that $g$ or $g+p$ is a primitive root modulo $p^a$ for a primitive root $g$ modulo $p$?

I wish to prove the following:

If $$p$$ is an odd prime and $$g$$ is a primitive root modulo $$p$$, then either $$g$$ or $$g+p$$ is a primitive root modulo every power of $$p$$.

The only reference I can find to this is on page 26 of "A Course in Computational Algebraic Number Theory" by Henri Cohen (https://books.google.no/books?id=hXGr-9l1DXcC&pg=PP1&dq=A+Course+in+Computational+Algebraic+Number+Theory&ei=98TxSsRYjeSTBP7p6egL&redir_esc=y#v=snippet&q=primitive&f=false)

I'm struggling to understand the dense proof presented there. I understand all the steps and statements, with the exception of the last part of the following:

For any $$m$$ we have $$m^p\equiv m\pmod{p}$$, hence it follows that for every prime $$l$$ dividing $$p-1$$, $$g^{p^{a-1}(p-1)/l}\equiv g^{(p-1)/l}\not\equiv 1\pmod{p}$$. So for $$g$$ to be a primitive root, we need only that $$g^{p^{a-2}(p-1)}\not\equiv 1\pmod{p^a}$$.

Here is my understanding: $$m^p\equiv m\pmod{p}$$ is just Fermat's little theorem, and by induction it also follows that $$m^{p^k}\equiv m\pmod{p}$$. By inserting $$a-1$$ for $$k$$ and $$g^{(p-1)/l}$$ for $$m$$, we obtain $$g^{p^{a-1}(p-1)/l}\equiv g^{(p-1)/l}\pmod{p}$$. Further, since $$g$$ is a primitive root modulo $$p$$, $$g^k\not\equiv 1\pmod{p}$$ holds for all $$k, in particular for $$k=(p-1)/l$$. Going from there to say that it is sufficient that $$g^{p^{a-2}(p-1)}\not\equiv 1\pmod{p^a}$$ for $$g$$ to be a primitive root modulo $$p^a$$, is beyond me. Could anybody please help me understand this step?

The rest of the proof after that point is pretty straightforward, although it omits a lot of details.

## 1 Answer

The order of $$g$$ mod $$p^a$$ has to divide $$p^{a-1}(p-1)$$ by Fermat-Euler, and you have shown you can't take out factors from $$p-1$$. So the order must be $$p^j(p-1)$$ for some $$0\leq j\leq a-1$$. Hence it suffices to impose the constraint $$g^{p^{a-2}(p-1)}\not\equiv 1\pmod{p^a}$$.