# Prove that it is not a primitive root module $p^2$

I don't even know how to start to prove the following...

Let $p$ be an odd prime. Prove that if $a$ is a primitive root modulo $p$ then exactly one of the following integers

$a,a+p,a+2p,...,a+(p-1)p$ is not a primitive root module $p^2$.

Thanks a lot :)

• From this, math.stackexchange.com/questions/1832701/… , we need to show for exactly one of $b=a+rp,0\le r<p;b^{p-1}\not\equiv1\pmod{p^2}$ – lab bhattacharjee Dec 27 '16 at 11:39
• Yeas, but how?... :( – Alopiso Dec 27 '16 at 13:52
• If $a$ is not a primitive $p^2$-th root of $1$, then its order mod $p^2$ must be $p-1$. Check that $(a + rp)^{p-1} \not\equiv 1 \bmod p^2$ for any $0 < r <p$ and you are done. – Derek Holt Dec 27 '16 at 14:47
• @Alopiso, Please find my answer – lab bhattacharjee Dec 27 '16 at 15:52

## 1 Answer

As $a+rp\equiv a\pmod p$ and as $a$ is a primitive root $\pmod p,$

$a+rp,1\le r\le p-1$ are also primitive root $\pmod p,$

By Question about primitive roots of p and $p^2$, ord$_{p^2}(a+rp)=p(p-1)$ or $p-1$ for $0\le r\le p-1$

Now we have $a^{p-1}=1+kp$ where $k$ is some integer

$(a+rp)^{p-1}\equiv a^{p-1}+(p-1)a^{p-2}rp\pmod{p^2}\equiv1+kp-a^{p-2}rp$

Now this will be $\equiv1\pmod{p^2}\iff k\equiv a^{p-2}r\pmod p\iff r\equiv ka$ as $a^{p-1}\equiv1\pmod p$

Clearly, there one such $r,0\le r\le p-1$ such that ord$_{p^2}(a+rp)=p-1$