For an odd prime $p$, show that:
(a) Any primitive root of $p^2$ is also a primitive root of $p$
(b) Any primitive root of $p^n$ is also a primitive root of $p$
For part (a):
$r$ is a primitive root $\pmod {p^2}$
Suppose $r$ is not a primitive root $\pmod p$. Then there is
some $n$ with $n|p−1$ by lagranges theorem. But then, $r^{np} \equiv 1 \pmod {p^2}$. Contradiction.
Is this okay? I Didn't use the p being odd assumption here!
I have the general idea for (b):
Let $r$ be a primitive root of $p^n$ then: for $(a,p)=1$:
$r^k\equiv a \pmod{p^n}$ $\Rightarrow r^k\equiv a \pmod{p}$
But how do we show the existence of $r$ & complete the proof?
Best Answer
I'll do (a), and leave (b) to you.
If $r=1+ap$, then $r^p=(1+ap)^p$. Expand to verify that every term except for the first is divisible by $p^2$.
Thus, if $x$ has multiplicative order $k$ modulo $p$, so that $x^k = 1+ap$ for some $a$, then $x$ has order dividing $kp$ modulo $p^2$; and the order modulo $p^2$ must be a multiple of $k$. Thus, the order of $x$ modulo $p^2$ will be either $k$ or $kp$, since $p$ is a prime.
In particular, if the order of $x$ modulo $p^2$ is $p(p-1)$, then the order of $x$ modulo $p$ must be $p-1$.