Question: 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.

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