$p$ is an odd prime. I'm starting with number theory and I'm completly stuck with this question. In general, I don't really know how to approach the proves. Then I'm also supposed to prove that either $g$ or $g+p$ is a primitive root modulo $p^2$ using that first result. I also know about quadratic residues and I think the problem is designed to use them as well.

EDIT: I realised one of the implications is straight-forward, as if $g^{p-1} \equiv 1 \mod{p^2}$, then the order of $g$ would be, at most, $p-1$, so it can't be a primitve root modulo $p^2$.

  • $\begingroup$ Is p prime here? Also is the title correct? I think it should be $g^{p-1} \not \equiv 1$ mod $p^2$ $\endgroup$
    – EnEm
    Sep 25, 2022 at 22:33
  • 1
    $\begingroup$ That's right, sorry. Now it's rightly edited $\endgroup$ Sep 25, 2022 at 22:40

1 Answer 1


$(\Rightarrow)$ As you said in the edit, if $g^{p-1} \equiv 1 \mod p^2$ then the order of $g$ in $\mod p^2$ is at most $p-1$. But, $\phi(p^2)=p(p-1)>p-1$. Hence, $g$ can't be a primitive root. Contradiction.

$(\Leftarrow)$ We have that $g^{p-1} \not \equiv 1 \mod p^2$. We denote $ord(g)$ the order of $g$ $\mod p^2$.

We know that $g^{ord(g)} \equiv 1 \mod p^2 \Rightarrow p^2|g^{ord(g)} - 1 \Rightarrow p|g^{ord(g)}-1 \Rightarrow g^{ord(g)} \equiv 1 \mod p$. Hence, $p-1|ord(g)$ because $g$ primitive root $\mod p$. Also, we know that $ord(g)|\phi(p^2) = p(p-1)$.

Since $p$ is prime, either $ord(g)|p-1$ or $ord(g)=p(p-1)$ (because $ord(g)$ won't divide neither $p$ nor $p-1$). If $ord(g)|p-1$ then, because $p-1|ord(g)$ we have that $ord(g)=p-1$, a contradiction as $g^{p-1} \not \equiv 1 \mod p^2$.

Therefore, $ord(g)=p(p-1)=\phi(p^2)$ and thus $g$ is a primitive root $\mod p^2$

For what you are finally supposed to show, you now know that if $g$ is a primitive root $\mod p^2$, $g^{p-1} \not \equiv 1 \mod p^2$ and $\textbf{vice versa}$. Now try to see what you can do if $g^{p-1} \equiv 1 \mod p^2$. What is $ord(g)$ now? Afterwards, as a hint, you can use the binomial theorem for $(g+p)^{p-1} \mod p^2$. What you observe now? Have we proved something similar for the value you found?


You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .