Primitive root challenge

[Poirot]

Show that if $x$ is a primitive root of p, and $x^{p-1}$ is not congruent to 1 mod$p^2$, then x is a primitive root of $p^2$

 

[caffeinemachine]

Re: primitive root challenge

Show that if $x$ is a primitive root of p, and $x^{p-1}$ is not congruent to 1 mod$p^2$, then x is a primitive root of $p^2$

We assume $p$ is an odd prime.

By Fermat, $x^{p-1}\equiv 1\pmod{p}$.
Thus $x^{p-1}=pk+1$. By hypothesis, $p\not |k$.
Let order of $x$ mod $p^2$ be $n$. Then $x^n\equiv 1\pmod{p}$, therefore $(p-1)|n$ (since order of $x$ mod $p$ is $p-1$).
Write $n=l(p-1)$.
So we have $x^n=(pk+1)^{l}\equiv 1\pmod{p^2}$.
So we have $lpk+1\equiv 1\pmod{p^2}$.
Thus $p|(lk)$.
Since $p$ doesn't divide $k$, we have $p|l$ and now its easy to show that $n=p(p-1)=\varphi(p^2)$ and we are done.

 

[Poirot]

Re: primitive root challenge

So we have $x^n=(pk+1)^{l}\equiv 1\pmod{p^2}$.

So we have $lpk+1\equiv 1\pmod{p^2}$.

What is the logic in this step?
Also, note the result is vacuously true when p=2.

 

[caffeinemachine]

Re: primitive root challenge

What is the logic in this step?
Also, note the result is vacuously true when p=2.

Hello Poirot,

By Binomial expansion we have $(1+pk)^l=1+pkl+p^2t$ for some integer $t$.
Now it should be clear I believe.