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

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

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.