TAOCP 3.2.1.2 Exercise 14
Assume $a$ is a primitive element modulo $p$, so that $a^{p-1} \equiv 1 \pmod{p}$ and $a^k \not\equiv 1 \pmod{p}$ for $1 \le k < p-1$.
Section 3.2.1.2: Choice of Multiplier
Exercise 14. [**] [M15] If $e > 1$ and $a$ is a primitive element modulo $p$, prove that either $a$ or $a + p$ is a primitive element modulo $p^e$. [Hint: See exercise 12.]
Verified: yes
Solve time: 1m53s
Assume $a$ is a primitive element modulo $p$, so that $a^{p-1} \equiv 1 \pmod{p}$ and $a^k \not\equiv 1 \pmod{p}$ for $1 \le k < p-1$. By exercise 12, $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}$. If $a^{p-1} \not\equiv 1 \pmod{p^2}$, then $a$ itself is a primitive element modulo $p^e$. Otherwise, $a^{p-1} \equiv 1 \pmod{p^2}$; in this case, consider $a + p$. We have
$(a + p)^{p-1} \equiv a^{p-1} + (p-1)a^{p-2} p \equiv a^{p-1} + (p-1) a^{p-2} p \not\equiv 1 \pmod{p^2},$
because $(p-1)a^{p-2}p$ is divisible by $p$ but not by $p^2$, so $(a + p)^{p-1} \not\equiv 1 \pmod{p^2}$. Therefore $a + p$ is a primitive element modulo $p^e$. This completes the proof. ∎