7
$\begingroup$

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.

  • 0
    @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.2011-08-23

3 Answers 3

11

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

  • 0
    @user1932595: I added to the original answer. Some computer trouble, have not been able to proofread, but it should be basically OK.2013-03-31
5

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

  • 0
    @Zev Chonoles: You are absolutely right, and that statement is totally invalid at all. I am again very sorry.2011-08-23
1

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.

  • 0
    Thanks for your answer, Zarrax.2011-08-06