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?
Best Answer
$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]$.