1. ## Primitive roots

Question:
Prove: If p and q=2p+1 are both odd primes, then -4 is a primitive root of q.

2. Note that when $q=2p+1$ then $\phi(q-1)=p-1=\tfrac{{q - 1}}
{2} - 1$
(1) . There are $\phi(q-1)$ primitive roots and $\tfrac{{q - 1}}
{2}$
non-quadratic residues, and each primitive root is a non-quadratic residue (because otherwise it'd only generate quadratic residues). Thus (1) means that all non-quadratic residues but 1 of them, are primitive roots.

We can show that the only non-quadratic residue that is not a primitive root is -1. Note that $q \equiv 3\left( {\bmod .4} \right)$ (consider p=1,3(mod.4) ), thus -1 is a non-quadratic residue mod. q. But ${\left( { - 1} \right)^2} \equiv 1\left( {\bmod .q} \right)$ thus -1 is not a primitive root.

Now just check that $- 4$ is a non-quadratic residue module q (easy because 4 is a square and -1 is a non-quadratic residue), and then check that $- 4 \not\equiv - 1\left( {\bmod .q} \right)$ and we are done.