Exercise 2.8.19 (if $g$ is a primitive root $\pmod{p^2}$, it is a primitive root $\pmod p$)

Question

Show that if $a^h\equiv 1 \pmod p$ then $a^{ph} \equiv 1 \pmod{p^2}$. Show that if $a$ is a primitive root $\pmod {p^2}$ then it is a primitive root $\pmod p$.

Richard Ganaye · Accepted Answer

\begin{proof} 
If $a^h\equiv 1 \pmod p$, then $a^h = 1 + kp$ for some integer $k$. Then
\begin{align*}
a^{ph} &= (1 + kp)^p\
&= 1 + \binom{p}{1} kp + \binom{p}{2} (kp)^2 + \cdots + \binom{p}{p} (kp)^p\
&\equiv 1 \pmod{p^2},
\end{align*}
because $\binom{p}{1} kp  = kp^2$, and all the other terms, except $1$, are divisible by $p^2$. Thus
$$a^{ph} \equiv 1 \pmod {p^2}.$$

\bigskip Suppose now that $a$ is a primitive root modulo $p^2$. Then for all positive integer $m$
$$a^m \equiv 1 \pmod{p^2} \iff \phi(p^2) \mid m \iff p(p-1) \mid m.$$

In particular, $a^{\phi(p^2)} \equiv 1 \pmod {p^2}$. A fortiori $a^{\phi(p^2)} \equiv 1 \pmod {p}$. Therefore,
since $a^p \equiv a$ by Fermat's theorem,  $a^{p-1} \equiv (a^{p})^{p-1} = a^{\phi(p^2)} \equiv 1 \pmod p$.

Moreover, by the first part, for all positive integers $h$,
\begin{align*}
a^h \equiv 1 \pmod p& \Rightarrow a^{ph} \equiv 1 \pmod{p^2}\
&\Rightarrow  p(p-1)\mid ph\
&\Rightarrow p-1 \mid h.
\end{align*}
Therefore $p-1$ is the least positive integer $h$ such that $a^{h} \equiv 1 \pmod p$. This shows that the order of $a$ modulo $p$ is $p-1 = \phi(p)$. Thus $a$ is a primitive root modulo $p$.
\end{proof}

Exercise 2.8.19 (if $g$ is a primitive root $\pmod{p^2}$, it is a primitive root $\pmod p$)

Answers

Comments

Exercise 2.8.19 (if $g$ is a primitive root $\pmod{p^2}$, it is a primitive root $\pmod p$)

Answers

Comments

Add answer