# A primitive root modulo p is a primitive root modulo $p^2$ if and only if $g^{p-1} \not\equiv 1 \mod{p^2}$

$$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$$.

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

$$(\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?