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<p-1$, 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.


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}$.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.