3
$\begingroup$

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!

$\endgroup$
1
  • $\begingroup$ May I ask where this problem is from? $\endgroup$
    – David
    Feb 11, 2016 at 4:39

1 Answer 1

2
$\begingroup$

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.

$\endgroup$
2
  • $\begingroup$ But how do we know that $g^{p(p-1)}\equiv 1\pmod{p^2}$? This doesn't seem obviously true to me! $\endgroup$ Feb 11, 2016 at 14:05
  • $\begingroup$ @user2973447: Note that $\varphi(p^2)=p(p-1)$. Now use the Fermat-Euler Theorem. $\endgroup$ Feb 11, 2016 at 14:39

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .