I know that someone has already posted this problem, but I wanted to see if my proof is also valid. Here is the problem:

Let $r$ be a primitive root of the odd prime $p$. Prove that if $p\equiv 3\pmod4$, then $-r$ has order $(p-1)/2$ modulo $p$.


Note that since $r$ is a primitive root of $p$, we have $r^{(p-1)/2}\equiv -1\pmod{p}$.

Suppose $o_p(-r)=m$, some $0<m<\frac{p-1}{2}$.

First suppose $m$ is even. Then, $(-r)^m=r^m$, so $(-r^m)\equiv 1\pmod{p}\implies r^m\equiv 1\pmod{p}$, which contradicts $r$ is a primitive root of $p$.

Now, suppose $m$ is odd. Then $(-r)^m=-r^m$, so $(-r^m)\equiv 1\pmod{p}\implies -r^m\equiv 1\pmod{p}\implies r^m\equiv -1\pmod{p}$.

But since $r$ is a primitive root of $p$, we have $r^{(p-1)/2}\equiv -1\pmod{p}$ (we had shown this in a previous problem). So $r^m\equiv -1\pmod{p}\implies m=\frac{p-1}{2}$, contradicting $m<\frac{p-1}{2}$.

Therefore, $o_p(-r)$ is not less than $\frac{p-1}{2}$.

I'm not sure where to go from here...

  • $\begingroup$ I solved, is there is something not clear comment that I edit. $\endgroup$ Nov 3, 2015 at 23:19
  • 1
    $\begingroup$ Thank you so much, I hadn't thought about doing it that way! $\endgroup$ Nov 9, 2015 at 9:08

1 Answer 1


Try this: Once $p \equiv 3 \pmod 4$ it means that $-1$ is not a square over $Z_p$. That's ok? Then, $(-r)^{\frac{p-1}{2}} \equiv (\frac{-1}{p})(\frac{r}{p}) \pmod p.$ Where $(\frac{}{})$ means the Legendre symbol. But $(\frac{-1}{p}) = -1$ and then $(-r)^{\frac{p-1}{2}} = 1,$ once $(\frac{r}{p}) = -1,$ since order of $r$ is $p-1$ and not $(p-1)/2$. Then we have proved that $(-r)^{\frac{p-1}{2}} \equiv 1 \pmod p$.

Now, suppose that the order of $(-r)$ is $m$ less then $(p-1)/2$. Then $2m = (p-1)/2$ and then $p \equiv 1 \pmod 4.$


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.