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.

  • 2
    $\begingroup$ More is needed than $(-a)^{(p-1)/2}\equiv 1 \pmod{p}$, need also fact nothing smaller works. $\endgroup$ – André Nicolas Aug 6 '11 at 23:41
  • $\begingroup$ @awllower: I don't understand your comment. It doesn't "assure that the quadratic reciprocity law is false". $\endgroup$ – Zev Chonoles Aug 21 '11 at 15:50
  • $\begingroup$ @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. $\endgroup$ – 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$.

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

  • $\begingroup$ Thanks Zev, your second to last paragraph ironed out what I wasn't seeing. $\endgroup$ – yunone Aug 6 '11 at 23:52
  • $\begingroup$ 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$? $\endgroup$ – awllower Aug 21 '11 at 9:06
  • $\begingroup$ @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$. $\endgroup$ – Zev Chonoles Aug 21 '11 at 15:47
  • $\begingroup$ @Zev Chonoles: You are absolutely right, and that statement is totally invalid at all. I am again very sorry. $\endgroup$ – 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.

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

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.