Primitive Roots Given $p$, $q$ both primes such that $q = 2p + 1$, I need to prove that $-4$ is a primitive root mod $q$. 
So far haven't found a direction that could lead me to the solution. 
Any suggestion or short solution would be helpful, thanks in advance.
 A: We use a counting argument that works well for these Sophie Germain prime situations. 
Modulo $q$, there are $\varphi(\varphi(q))$ primitive roots. In our case, we have $\varphi(\varphi(q))=p-1$, so there are $p-1$ primitive roots of $q$.
But there are only $p$ quadratic non-residues of $q$. So every quadratic non-residue of $q$ except one is a primitive root of $q$. Since $p$ is odd, it is of the form $2k+1$. So $q$ is of the form $4k+3$, and therefore $-1$ is a quadratic non-residue of $q$, and obviously not a primitive root. 
Thus every quadratic non-residue of $q$ other than $-1$ is a primitive root of $q$. Finally, $-4$ is a quadratic non-residue, since $-1$ is a non-residue.  So $-4$ is a primitive root of $q$. 
A: The order of $-4$ can only be $1,2,p,2p$. It is easy to whos that it is not $1,2$ thus we only need to show it is not $p$.  
Since $(-4)^{\frac{q-1}{2}}=\pm 1 \pmod q$ you need to prove that $(-4)^{\frac{q-1}{2}} \equiv -1 \pmod q$. This is the same as showing that $4^{\frac{q-1}{2}} \equiv 1 \pmod q$. 
Hint $4=2^2$.
A: To prove that $-4$ is a primitive root modulo $q$, we need to show that the order of $-4$ is $q-1$, which is equivalent to showing that $(-4)^{\frac{q-1}{2}} \equiv_q -1$.
Assume that $p\neq2$. It follows that
$$(-4)^{\frac{q-1}{2}} \equiv_q -1 \iff 4^{\frac{q-1}{2}} \equiv_q 1 \iff 2^{q-1} \equiv_q 1$$
But this is true by Fermat's little theorem, since $q=2p+1$ is odd and thus does not divide $2$.
However, if $p=2$, then $q=5$ and $-4 \equiv_5 1$, so in this case the statement is not true.
