TAOCP 3.2.1.2 Exercise 12
**Solution.
Section 3.2.1.2: Choice of Multiplier
Exercise 12. [**] [M26] Let $p$ be an odd prime. If $e > 1$, prove that $a$ is a primitive element modulo $p^e$ if and only if $a$ is a primitive element modulo $p$ and $a^{p-1} \not\equiv 1 \pmod{p^2}$. (For the purposes of this exercise, assume that $\lambda(p^e) = p^{e-1}(p-1)$. This fact is proved in exercises 14 and 16 below.)
Verified: yes
Solve time: 4m57s
Solution.
Let
$$ \operatorname{ord}_{m}(a) $$
denote the order of $a$ modulo $m$. Since $\lambda(p^e)=p^{e-1}(p-1)$, $a$ is primitive modulo $p^e$ if and only if
$$ \operatorname{ord}_{p^e}(a)=p^{e-1}(p-1). $$
We shall use the following elementary fact.
Lemma. Let $r\ge1$, and suppose
$$ a^{n}=1+c,p^{,r}, \qquad p\nmid c . $$
Then
$$ a^{np}=1+c,p^{,r+1}+(\text{multiple of }p^{,r+2}). $$
Hence
$$ v_p(a^{np}-1)=v_p(a^n-1)+1=r+1 . $$
Proof. By the binomial theorem,
$$ a^{np}=(1+c,p^r)^p =1+pc,p^r+\sum_{j=2}^{p}\binom pj c^j p^{rj}. $$
Since $p$ is prime, $\binom pj$ is divisible by $p$ for
$1\le j\le p-1$. Thus every term with $j\ge2$ is divisible by
$p^{r+2}$. Therefore
$$ a^{np}=1+c,p^{r+1}+(\text{multiple of }p^{r+2}), $$
and the result follows. ∎
From the lemma, if $v_p(a^n-1)=r$, then
$$ v_p(a^{np^t}-1)=r+t \qquad (t\ge0). $$
We now prove the theorem.
Necessity
Assume that $a$ is primitive modulo $p^e$. Then
$$ \operatorname{ord}_{p^e}(a)=p^{e-1}(p-1). $$
Let
$$ d=\operatorname{ord}_{p}(a). $$
Reduction modulo $p$ shows that $d\mid \operatorname{ord}_{p^e}(a)$. Since also $d\mid p-1$,
$$ d\mid p-1. $$
Suppose $d<p-1$. Then $a^d\equiv1\pmod p$, so write
$$ v_p(a^d-1)=r\ge1. $$
Applying the lemma repeatedly,
$$ v_p!\left(a^{d p^{,e-r}}-1\right)=e. $$
Hence
$$ a^{d p^{,e-r}}\equiv1\pmod{p^e}. $$
Therefore
$$ \operatorname{ord}_{p^e}(a)\mid d p^{,e-r} \le d p^{,e-1} < (p-1)p^{,e-1}, $$
contrary to
$$ \operatorname{ord}_{p^e}(a)=p^{e-1}(p-1). $$
Thus $d=p-1$, and $a$ is primitive modulo $p$.
Next suppose
$$ a^{p-1}\equiv1\pmod{p^2}. $$
Since $\operatorname{ord}_{p}(a)=p-1$, this implies
$$ v_p(a^{p-1}-1)\ge2. $$
Applying the lemma repeatedly,
$$ v_p!\left(a^{(p-1)p^{e-2}}-1\right)\ge e. $$
Hence
$$ a^{(p-1)p^{e-2}}\equiv1\pmod{p^e}, $$
so
$$ \operatorname{ord}_{p^e}(a)\mid (p-1)p^{e-2}, $$
which is impossible because
$$ \operatorname{ord}_{p^e}(a)=p^{e-1}(p-1). $$
Therefore
$$ a^{p-1}\not\equiv1\pmod{p^2}. $$
This proves the necessity.
Sufficiency
Assume that
$$ \operatorname{ord}_{p}(a)=p-1 $$
and
$$ a^{p-1}\not\equiv1\pmod{p^2}. $$
Let
$$ n=p-1. $$
Since $a^n\equiv1\pmod p$ but not modulo $p^2$,
$$ v_p(a^n-1)=1. $$
By repeated application of the lemma,
$$ v_p!\left(a^{n p^{,t}}-1\right)=t+1 \qquad (t\ge0). $$
In particular,
$$ v_p!\left(a^{(p-1)p^{e-2}}-1\right)=e-1, $$
so
$$ a^{(p-1)p^{e-2}}\not\equiv1\pmod{p^e}, $$
while
$$ v_p!\left(a^{(p-1)p^{e-1}}-1\right)=e, $$
hence
$$ a^{(p-1)p^{e-1}}\equiv1\pmod{p^e}. $$
Let
$$ m=\operatorname{ord}_{p^e}(a). $$
Then $m\mid (p-1)p^{e-1}$.
If $m$ were a proper divisor of $(p-1)p^{e-1}$, then, because
$\operatorname{ord}_{p}(a)=p-1$, we would have
$$ m\mid (p-1)p^{e-2}. $$
Consequently
$$ a^{(p-1)p^{e-2}}\equiv1\pmod{p^e}, $$
contradicting the previous paragraph.
Therefore
$$ m=(p-1)p^{e-1}. $$
Since $\lambda(p^e)=p^{e-1}(p-1)$,
$$ \operatorname{ord}_{p^e}(a)=\lambda(p^e), $$
and $a$ is primitive modulo $p^e$.
Hence $a$ is a primitive element modulo $p^e$ if and only if $a$ is a primitive element modulo $p$ and
$$ a^{p-1}\not\equiv1\pmod{p^2}. $$
∎