# Number Theory: If $p\equiv 3\pmod{4}$, then $-r$ has order $(p-1)/2$ modulo $p$.

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

Proof

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

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

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