# If $-a$ has order $(p-1)/2$ mod $p$, why then is $a$ a primitive root?

I'm trying to solve a little exercise about primitive roots.

Consider a prime $p$ of the form $4q+3$. Prove that $a$ is a primitive root modulo $p$ if and only if $-a$ has order $(p-1)/2$.

I was able to prove the forward implication. To prove the other one, I'm assuming $(-a)^{(p-1)/2}\equiv 1\pmod{p}$, and trying to prove if $a^k\equiv 1\pmod{p}$, then $p-1|k$ to see $a$ is a primitive root. If $k$ is even, then $$a^k\equiv (-a)^k\equiv 1\pmod{p},$$ so $(p-1)/2|k$, or $p-1|2k$. If $k$ is odd, then I get that $$a^k\equiv -(-a)^k\equiv 1\pmod{p},$$ so $(-a)^{2k}\equiv 1\pmod{p}$. Then $p-1|4k$. I'm not sure I'm heading in the right direction. How can I finish up this argument, if possible? Thanks.

• More is needed than $(-a)^{(p-1)/2}\equiv 1 \pmod{p}$, need also fact nothing smaller works. – André Nicolas Aug 6 '11 at 23:41
• @awllower: I don't understand your comment. It doesn't "assure that the quadratic reciprocity law is false". – Zev Chonoles Aug 21 '11 at 15:50
• @Zev Chonoles: If $p \equiv 1 \pmod{4}$, and $-a$ has order $(p-1)/2$ modulo $p$, then this means that $a^{(p-1)/2}\equiv 1 \pmod{p}$; how can $a$ be a primitive root modulo $p$ then? Of course my previous comment means that $(-1)^{(p-1)/2}\equiv 1 \pmod{p}$, mistakenly read as the failure of the quadratic reciprocity law by me. I am very sorry about that; and I have deleted the comment. – awllower Aug 23 '11 at 2:07

Do you know the theorem that says that if the orders of $c$ and $d$ are relatively prime, then the order of $cd$ is the product of the orders of $c$ and $d$?

The above result takes care of your problem. For suppose that $-a$ has order $(p-1)/2$. Since $p$ is of the form $4k+3$, $(p-1)/2$ is odd.

Also, $-1$ has order $2$. Thus the order of $(-1)(-a)$ is $p-1$.

Appendix: We prove the useful result about the order of a product. Suppose that $h$ is the order of $c$, and $k$ is the order of $d$.

Let $r$ be the order of $cd$. Clearly $$(cd)^{hk}=(c^h)^k (d^k)^h \equiv 1 \pmod{p}$$ and hence $r\mid hk$.

Also, $$d^{rh}\equiv (c^h)^rd^{rh}\equiv (cd)^{rh}\equiv 1 \pmod{p}$$ and hence $k \mid rh$. Since $(h,k)=1$, it follows that $k \mid r$. Similarly, $h \mid r$, and therefore $hk \mid r$, since $(h,k)=1$.

Since $r \mid hk$ and $k \mid r$, we conclude that $r=hk$.

Added: We only did one direction, since OP wrote that he had done the other direction. But for completeness, and in response to a request, we write out the part OP had no problem with. Let $p$ be a prime of the form $4k+3$, and suppose that $a$ is a primitive root of $p$. We show that $-a$ has order $(p-1)/2$.

Because $a$ is a primitive root, it is a quadratic non-residue. But $p$ has shape $4k+3$, so $-1$ is a quadratic non-residue. So $(-1)a$ is a quadratic residue. It follows that the order of $-a$ cannot be $p-1$. If the order of $-a$ is $e$, we have $(-a)^{2e}=a^{2e}\equiv 1\pmod{p}$. Thus $p-1$ divides $2e$, and therefore $e=(p-1)/2$.

• Oh, that theorem wasn't mentioned. That's good to know, thanks. – yunone Aug 6 '11 at 23:49
• @yunone: I have added a proof of the product result. – André Nicolas Aug 7 '11 at 0:06
• Thanks André, I was going to look it up, but this saves me the trouble! Much appreciated. – yunone Aug 7 '11 at 0:15
• how to prove the other direstion? – user1932595 Mar 30 '13 at 22:49
• @user1932595: Have to go out. Will not get to your question for $6$ hours at least. – André Nicolas Mar 30 '13 at 23:09

The key to this problem is that $\frac{p-1}{2}$ is odd.

By definition, $a$ is a primitive root mod $p$ iff the order of $a$ is $p-1$.

The order of $-a$ is $\frac{p-1}{2}=2q+1$, which is odd. The order of $-1$ mod $p$ is $2$, which is even. Suppose $$a^k=(-1)^k(-a)^k\equiv1\bmod p.$$ If $k$ is even, then $a^{k}=(-a)^k\equiv 1\bmod p$, hence $k$ must be a multiple of $\frac{p-1}{2}$. But the even multiples of $\frac{p-1}{2}$ are precisely the multiples of $p-1$ itself, so $k$ must be a multiple of $p-1$.

If $k$ is odd, then $(-a)^k\equiv -1\bmod p$. But if $x^r=y$ for some $r\in\mathbb{N}$, then the order of $y$ divides the order of $x$, so the order of $-1$ (which is 2) divides the order of $-a$, which is $\frac{p-1}{2}=2q+1$, an odd number; contradiction.

Thus, the order of $a$ must be $p-1$.

• Thanks Zev, your second to last paragraph ironed out what I wasn't seeing. – yunone Aug 6 '11 at 23:52
• Why not use: As $\frac{p-1}{2}$ is odd, $a^{\frac{p-1}{2}} \equiv -1 \pmod p$, i.e. $a$ is a primitive root modulo $p$? – awllower Aug 21 '11 at 9:06
• @awllower: Just because $a^{\frac{p-1}{2}}\equiv-1\bmod p$ doesn't mean that $a$ is a primitive root mod $p$ (otherwise, there would be $\frac{p-1}{2}$ primitive roots mod $p$, instead of $\phi(p-1)$). For example, $$(-1)^\frac{7-1}{2}\equiv-1\bmod 7$$ but $-1$ obviously isn't a primitive root mod $7$. – Zev Chonoles Aug 21 '11 at 15:47
• @Zev Chonoles: You are absolutely right, and that statement is totally invalid at all. I am again very sorry. – awllower Aug 23 '11 at 2:11

What you're doing basically works... just assume $k$ is the order of $a$ (i.e. the least $k$ such that $a^k \equiv 1 \pmod p$). As in the problem, write $p = 4q + 3$. When $k$ is even, you've shown $2k$ is a multiple of $4q + 2$, so that $k$ is a multiple of $2q + 1$. Since $k$ is even, you must have $k = 4q + 2$ and you're done.

If $k$ is odd, you've shown $4k$ is a multiple of $4q + 2$, so that $2k$ is a multiple of $2q + 1$. Since $2q + 1$ is odd, $k$ is a multiple of $2q + 1$ as well. Since $k$ is the order of $a$ it divides $p - 1 = 4q + 2$. The only odd multiple of $2q + 1$ doing that is $k = 2q + 1$ itself. But in this case $(-a)^k \equiv -a^k \equiv -1 \pmod p$ by virtue of the fact that $-a$ is of order $2q + 1$ here. So a contradiction arises; this situation can't happen and you're done.

• Thanks for your answer, Zarrax. – yunone Aug 6 '11 at 23:54