Prove that every primitive root of $p^2$ is also a primitive root of $p^n$ for $n\ge 2$.
Yatir

Let $h$ be a primitive root (mod $p^2$). Using induction on $n$ we will show that $h$ is a primitive root (mod $p^n$) for all $n\ge 2$. Suppose $h$ is a primitive root (mod $p^n$) for $n\ge 2$, and let $d$ be the order of $h$ (mod $p^{n+1}$).

Euler's theorem implies $d$ divides $\varphi (p^{n+1})=p^n(p-1)$.

$h^d\equiv 1$ (mod $p^{n+1}$ ) $\Rightarrow h^d\equiv 1$ (mod $p^n$).

BUT $h$ has order $\varphi (p^n)=p^{n-1}(p-1)$ (mod $p^n$).

$\Rightarrow d=p^n(p-1)$ or $d=p^{n-1}(p-1)$

In the first case $h$ is a primitive root (mod $p^{n+1}$).

it is only necessary to prove that $h^{p^{n-1}(p-1)}\ne 1$ (mod $p^{n+1}$).

Since $h$ is a primitive root (mod $p^n$), it has order $\varphi (p^n)=p^{n-1}(p-1)$ in $U_{p^n}$, so $h^{p^{n-2}(p-1)}\ne 1$ (mod $p^n$). However $p^{n-2}(p-1)=\varphi (p^{n-1})$, so $h^{p^{n-2}(p-1)}\equiv 1$ (mod $p^{n-1}$) by Euler's theorem.

Thus we can see that $h^{p^{n-2}(p-1)}=1+k{p}^{n-1}$ where $gcd(k,p)=1$, so the binomial theorem gives

$h^{p^{n-1}(p-1)}=(1+k{p}^{n-1}{)}^p=1{+}^p{C}_{1}k{p}^{n-1}{+}^p{C}_2(k{p}^{n-1}{)}^2+\dots =1+k{p}^n+(1/2)k^2{p}^{2n-1}(p-1)+\dots$

The dots represent terms divisible by $(p^{n-1}{)}^3$ and hence by $p^{e+1}$.

$h^{p^{n-1}(p-1)}\equiv 1+k{p}^n+(1/2)k^2{p}^{2n-1}(p-1)$ (mod $p^{n+1}$)

$p$ is odd $\Rightarrow k^2{p}^{2n-1}(p-1)/2$ is also divisible by $p^{n+1}$. Thus

$h^{p^{n-1}(p-1)}\equiv 1+k{p}^n$ (mod $p^{n+1}$)

Since $p$ does not divide $k$, we have $h^{pn-1(p-1)}\ne 1$ (mod $p^{n+1}$).

$\Rightarrow$ if $h$ is any primitive root (mod $p^2$), then $h$ is a primitive root (mod $p^n$) for all $n\ge 2$.

Henry