- Thread starter
- Banned
- #1

- Thread starter Poirot
- Start date

- Thread starter
- Banned
- #1

- Mar 10, 2012

- 834

We assume $p$ is an odd prime.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$

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.

- Thread starter
- Banned
- #3

What is the logic in this step?So we have $x^n=(pk+1)^{l}\equiv 1\pmod{p^2}$.

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

Also, note the result is vacuously true when p=2.

- Mar 10, 2012

- 834

Hello Poirot,What is the logic in this step?

Also, note the result is vacuously true when p=2.

By Binomial expansion we have $(1+pk)^l=1+pkl+p^2t$ for some integer $t$.

Now it should be clear I believe.