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