# If $p \equiv 3 \mod 4$ and $r$ primitive root, then $\mathrm{ord}_p(-r) = (p-1)/2$

I've been looking at a bunch of number theory problems lately and I need help with a few. One of them is as follows:

Let $p$ be a prime number with $p \equiv 3 \mod 4$ and let $r$ be a primitive root modulo $p$. Prove that $\mathrm{ord}_p(-r) = (p-1)/2$.

First we note that $p=4k+3$ and $(p-1)/2=2k+1$. My idea so far has been to use that $r$ is a primitive root, so $$r^{p-1}\equiv 1 \mod p$$ or $$r^{4k+2} = r^{2(2k+1)} = \left( r^{2k+1}\right)^{2} \equiv 1 \mod p.$$ Hence $r^{2k+1}\equiv \pm 1 \mod p$, but since $r$ is a primitive root we must have $r^{2k+1} \equiv -1 \mod p$. Hence $-(r)^{2k+1} \equiv 1$, or, since $2k+1$ is odd, $$(-r)^{2k+1} \equiv 1 \mod{p}.$$ Is this the correct way of going about it?

The argument is good, but it has not been shown that $-r$ has order $\frac{p-1}{2}$. What has been shown is that the order of $-r$ divides $\frac{p-1}{2}$.

But the ideas you used lead quickly to the finish. If $-r$ has order $q\lt 2k+1$, where $p=4k+3$, then since $q$ is odd we have $r^q\equiv -1\pmod{p}$, and therefore $r^{2q}\equiv 1\pmod{p}$. Since $2q\lt p-1$, this contradicts the fact that $r$ is a primitive root of $p$.

• You are welcome. You had all the required tools, just a missing detail that used the same tools. – André Nicolas Nov 19 '13 at 8:30