If $g$ is a primitive root of $p^2$ where $p$ is an odd prime, why is $g$ a primitive root of $p^k$ for any $k \geq 1$?

I saw this theorem referenced in a paper on performing shuffles in an array. There is a proof on pages 20-21 of the this link, but the proof is very terse and omits a lot of intuition.

Is there an intuitive explanation for why this theorem is true, or at least a proof that omits fewer details?

-
When I follow that link, I see the message "pages 3-98 are not shown in this preview". – Matthew Conroy Apr 8 '11 at 4:55
Wow, I don't know why it gave me so much more of a preview. – jonderry Apr 8 '11 at 7:16
See my answer here: math.stackexchange.com/questions/25849/… It is a little more intuitive, but also more advanced than you might want. I doubt there is an extremely intuitive reason that is also accesible when you are first learning this stuff. – Barry Smith Apr 8 '11 at 10:50

First we claim that for any $k\geq 0$ we can write $$g^{p^{k-1}p}=1+a_kp^k\qquad\text{where }p\nmid a_k$$ Clearly $g^{p-1}\equiv 1\pmod{p}$ and hence $g^{p-1}=1+a_0p$ for some $a_0$. Note that $p\nmid a_0$ because otherwise $g^{p-1}\equiv 1\pmod{p^2}$ (contradiction to the fact that $g$ is a primitive root mod $p^2$). Assume that $g^{p^{s-1}p}=1+a_sp^s$ where $p\nmid a_s$. It follows $$g^{p^s(p-1)}=1+a_sp^{s+1}+ \text{ multiple of }p^{s+2}=1+a_{s+1}p^{s+1}$$ If $p\mid a_{s+1}$ then $p^{s+2}\mid a_sp^{s+1}$ which implies that $p\mid a_s$ (contradiction!). Thus $p\nmid a_{s+1}$.

Now we claim that for $k\geq 2$, the order of $g$ mod $p^k$ is $p^{k-1}(p-1)$. For $k=2$, the statement is true. Assume the order of $g$ mod $p^s$ is $p^{s-1}(p-1)$. Since $$g^{p^s(p-1)}=1+a_{s+1}p^{s+1}$$ clearly $g^{p^s(p-1)}\equiv 1\pmod {p^{s+1}}$. Suppose $l$ be a number such that $g^l\equiv 1\pmod {p^{s+1}}$. Then obviously $g^l\equiv 1\pmod{p^s}$. Since $p^{s-1}(p-1)$ is the order of $g$ mod $p^s$, then $l=tp^{s-1}(p-1)$. Now $$g^l=g^{tp^{s-1}(p-1)}=1+ta_sp^s+\text{ multiple of }p^{s+1}$$ Since $g^l\equiv 1\pmod {p^{s+1}}$ then $p^{s+1}\mid ta_sp^{s}$. But $p\nmid a_s$. Hence $p\mid t$. Write $t=pt_2$. It follows that $l=t_2p^s(p-1)$ and we conclude that $p^s(p-1)$ is the order of $g$ mod $p^{s+1}$.

The case that $g$ is primitive root mod $p$ is left to the reader :).

-
Don't you mean $g^{p^{k - 1}(p - 1)}$, and similarly with some of the other expressions? – jonderry Apr 10 '11 at 18:28