1
$\begingroup$

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

$\endgroup$
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

2
$\begingroup$

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

$\endgroup$

You must log in to answer this question.

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