Prove that , any primitive root $r$ of $p^n$ is also a primitive root of $p$

For an odd prime $p$, prove that any primitive root $r$ of $p^n$ is also a primitive root of $p$

So I have assumed $r$ have order $k$ modulo $p$ , So $k|p-1$.Then if I am able to show that $p-1|k$ then I am done .But I haven't been able to show that.Can anybody help me this method?Any other type of prove is also welcomed.

Solution 1:

For any $a$ relatively prime to $p^n$, there is an integer $k$ such that $r^k\equiv a \pmod{p^n}$ and hence such that $r^k \equiv a\pmod{p}$. Thus $r$ is a primitive root of $p$.

Solution 2:

Note that an integer $r$ with $\gcd(r,p)=1$ is a primitive root modulo $p^k$ when the smallest $b$ such that $r^b\equiv1\bmod p^k$ is $b=p^{k-1}(p-1)$.

Suppose that $r$ is not a primitive root modulo $p$, so there is some $b<p-1$ such that $r^b\equiv 1\bmod p$.

In other words, there is some integer $t$ such that $r^b=1+pt$.

Then of course we have that $p^{n-1}b<p^{n-1}(p-1)$, and $$r^{p^{n-1}b}\equiv 1\bmod p^n$$ because of

the binomial theorem.

(mouse over to reveal spoilers)