Can a Primitive Root of p Also Be a Primitive Root of p^2?

[Poirot1]

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.

 

[Poirot1]

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.

 

[CellCoree]

To show that $x$ is a primitive root of $p^2$, we must show that it generates all the elements in the group of units modulo $p^2$. If $x$ is a primitive root of $p$, then it generates all the elements in the group of units modulo $p$.

Now, since $x^{p-1}$ is not congruent to 1 modulo $p^2$, it means that $x^{p-1}$ is not a multiple of $p^2$. This implies that $x^{p-1}$ is not a multiple of $p$, since $p$ is a prime number.

Since $x^{p-1}$ is not a multiple of $p$, it follows that $x^{p-1}$ is relatively prime to $p$. Therefore, $x^{p-1}$ generates all the elements in the group of units modulo $p$.

Now, we can use the fact that $x$ is a primitive root of $p$ to show that $x$ is also a primitive root of $p^2$. Since $x^{p-1}$ generates all the elements in the group of units modulo $p$, it follows that $x^{p-1}$ also generates all the elements in the group of units modulo $p^2$.

This shows that $x$ is a primitive root of $p^2$, as it generates all the elements in the group of units modulo $p^2$. Thus, if $x$ is a primitive root of $p$ and $x^{p-1}$ is not congruent to 1 modulo $p^2$, then $x$ is also a primitive root of $p^2$.