Proof. From Theorem 8.8, we know that $p$ has a primitive root $r$ that is also a primitive root modulo $p^{2}$, so that
$$r^{p-1} \not \equiv 1\left(\bmod p^{2}\right)$$

Using mathematical induction, we will prove that for this primitive root r ,
$$r^{p^{k-2}(p-1)} \not \equiv 1\left(\bmod p^{k}\right)$$
for all positive integers k . Once we have established this congruence, we can show that $r$ is also a primitive root modulo $p^{k}$ by the following reasoning. Let
$$n=\text { ord }_{p^{*}} \varepsilon \text {. }$$

From Theorem 6.8 , we know that $n \mid \phi\left(p^{k}\right)=p^{k-1}(p-1)$. On the other hand, since
$$r^{n} \equiv 1\left(\bmod p^{k}\right)$$
we also know that
$$r^{n} \equiv 1(\bmod p)$$

From Theorem 8.1, we see that $p-1=\phi(p) \mid n$. Because $(p-1) \mid n$, and $n \mid p^{k-1}(p-1)$, we know that $n=p^{t}(p-1)$, where $t$ is an integer such that $0 \leqslant t \leqslant k-1$. If $n=p^{t}(p-1)$ with $t \leqslant k-2$, then
$$r^{p^{k-2}(p-1)}=\left(r^{p^{\prime}(p-1)}\right)^{p^{k-2-1}} \equiv 1\left(\bmod p^{k}\right)$$
which would contradict (8.3). Hence, ord ${ }^{k} r=p^{k-1}(p-1)=\phi\left(p^{k}\right)$. Consequently, $r$ is also a primitive root modulo $p^{k}$.

All that remains is to prove (8.3) using mathematical induction. The case of $k=2$ follows from (8.2). Let us assume the assertion is true for the positive integer $k \geqslant 2$. Then
$$r^{p^{k-2}(p-1)} \not \equiv 1\left(\bmod p^{k}\right)$$

Since $(r, p)=1$, we know that $\left(r, p^{k-1}\right)=1$. Consequently, from Euler's theorem, we know that
$$r^{p^{k-2}(p-1)} \equiv r^{\phi\left(p^{k-1}\right)}$$

Therefore, there is an integer $d$ such that
$$r^{p^{k-2}(p-1)}=1+d p^{k-1}$$
where $p \backslash d$, since by hypothesis $r^{p^{t-2}(p-1)} \not \equiv 1\left(\bmod p^{k}\right)$. We take the $p$ th power of both sides of the above equation, to obtain, via the binomial theorem,
$$\begin{aligned} r^{p^{k-1}(p-1)} & =\left(1+d p^{k-1}\right)^{p} \\ & =1+p\left(d p^{k-1}\right)+\binom{p}{2} p^{2}\left(d p^{k-1}\right)^{2}+\cdots+\left(d p^{k-1}\right)^{p} \\ & \equiv 1+d p^{k}\left(\bmod p^{k+1}\right) \end{aligned}$$

Since $p \nmid d$, we can conclude that
$$r^{p^{k-1}(p-1)} \not \equiv 1\left(\bmod p^{k+1}\right)$$

This completes the proof by induction.