# Show that $g^p (1 + p)$ is a primitive root modulo $p^e$

Given that g is a primitive root modulo $p$, show that $g^p (1 + p)$ is a primitive root modulo $p^e$.

I'm not really sure where to go with this. the $gcd(p^e, g^p (1 + p))$ is easy enough to show to be $1$ but I'm not sure how to show that the order of [g] in $U$ is the same as the order of $U-$ or that this is the method that I should be aiming for. I was thinking that I could just show it for $p^2$ and then use that primitive roots modulo $p^2$ are also primitive roots for $p^e$ but proving that it is a primitive root modulo $p^2$ isn't proving to be much easier to do!

• May I ask where this problem is from? Feb 11, 2016 at 4:39

We show that $g^p(1+p)$ is a primitive root of $p^2$, and hence, as you observed, of $p^k$ for all $k$.
Note that $g^p(1+p)$ is a primitive root of $p$, since it is congruent to $g$ modulo $p$.
In general, if $a$ is a primitive root of $p$, then $a$ is a primitive root of $p^2$ precisely if $a^{p-1}\not\equiv 1\pmod{p^2}$. Now compute. We have $$(g^p(1+p))^{p-1}=g^{p(p-1)}(1+p)^{p-1}.$$ But $g^{p(p-1)}\equiv 1\pmod{p^2}$, and by the Binomial Theorem $(1+p)^{p-1}\not\equiv 1\pmod{p^2}$. Thus $(g^p(1+p))^{p-1}\not\equiv 1\pmod{p^2}$, and the result follows.
• But how do we know that $g^{p(p-1)}\equiv 1\pmod{p^2}$? This doesn't seem obviously true to me! Feb 11, 2016 at 14:05
• @user2973447: Note that $\varphi(p^2)=p(p-1)$. Now use the Fermat-Euler Theorem. Feb 11, 2016 at 14:39