# If $r$ is a primitive root of $p$ and $p^2$, then show that it is also a primitive root of $p^3$

If $$r$$ is a primitive root of $$p$$ and $$p^2$$, then show that it is also a primitive root of $$p^3$$

This is part of a bigger proof and I'm stuck at understanding this part.

Here some lines of proof from my textbook:

$$r^{p-1}\equiv 1 \pmod{p}$$
$$r^{p-1}\not\equiv 1 \pmod{p^2}$$

By Euler,
$$r^{\phi(p^2)} = r^{p(p-1)}\equiv 1\pmod{p^2}$$
$$\Rightarrow r^{p(p-1)} = 1 + ap^2$$ for some integer $$a$$.

Then my textbook simply claims $$p\nmid a$$ by hypothesis.
I don't get this. Why can't $$p$$ divide $$a$$ ? How does it follow from hypothesis?

$$r^{p-1} = 1 + kp$$. So $$r^{p(p-1)} = \sum_{j=0}^p \binom{p}{j}k^j p^j = 1 + kp^2 + lp^3$$ because of the fact that $$p|\binom{p}{j}$$ for $$2\le j\le p$$. So $$k + lp= a$$. If $$p|a$$ then $$p|k$$ and so $$r^{p-1} \equiv 1 \left[p^2\right]$$.
• Neat! Thank you so much for the quick response:) If I may ask is it obvious that $p\mid a \Rightarrow p\mid k$ without spending lots of time. Because I spent more than an hour on this and couldn't figure out on my own... :( Sep 12, 2021 at 4:11
• Yes because $a = k + lp$ which means that $p | k - a$. If also $p | a$ then $p | k$ because $k = k-a + a$. Sep 12, 2021 at 4:14
• +1. BTW: If $p$ is an odd prime and if $s$ is a primitive root mod $p$ but s is not a primitive root mod $p^2$ then $s+p$ is a primitive root mod $p^n$ for all $n\in\Bbb N.$ Sep 12, 2021 at 9:00