Let $p, q$ be odd primes with $p = 2q + 1$ Show that $2$ is a primitive root modulo $p$ if and only if $q\equiv1\pmod4$ Let $p,q$ be odd primes with $p = 2q + 1$
Show that $2$ is a primitive root modulo $p$ if and only if $q\equiv1\pmod4$
 A: One direction is easy. If $q\equiv 3\pmod{4}$, then $p\equiv -1\pmod{8}$, and therefore $2$ is a quadratic residue of $p$, so cannot be a primitive root. For this direction, the primality of $q$ was not used. 
We now show that if $q$ is a prime of shape $4k+1$, then $2$ is a primitive root of $p$.
If $q\equiv 1\pmod{4}$, then $p\equiv 3\pmod{8}$, so $2$ is a quadratic non-residue of $p$. That means that $2$ has a chance to be a primitive root of $p$. We check that indeed it is. 
We give a proof via a counting argument. There are $(p-1)/2=q$ incongruent quadratic non-residues of $p$. And by a general result, there are $\varphi(\varphi(p))$ primitive roots of $p$. (Here $\varphi$ is the Euler $\varphi$-function.) If $p=2q+1$ where $q$ is prime, then $\varphi(\varphi(p))=\varphi(2q)=q-1$, since $q$ is prime.
Since there are $q$ non-residues, and $q-1$ primitive roots, all but one non-residue must be a primitive root. Note that since $p$ has shape $4k+3$, $-1$ is a non-residue of $p$. But $-1$ is obviously not a primitive root of $p$. Therefore *every non-residue of $p$ other than $-1$ must be a primitive root of $p$. Since $2$ is a non-residue, this completes the proof.
A: So, $ord_p2=p-1=2q\implies 2^{2q}\equiv 1\pmod p\implies p\mid(2^q-1)(2^q+1)$
$2^{\frac{p-1}2}\equiv -1\pmod p$ as $2^q\equiv 1\pmod p\implies ord_p2\mid q,$ but $2q∤q$
$\implies 2$ is a quadratic non-residue of $p$
We know , $2$ is a quadratic residue of $p$ if $p\equiv\pm1\pmod 8$ (see here)
$\implies p=\pm3+8k$ for some integer $k$ for quadratic non-residue.
$2q+1=\pm3+8k$
If $2q+1=-3+8k,2q=8k-4,q=4k-2$ not odd,
So, $2q+1=3+8k,2q=8k+2,q=4k+1$
Conversely, if $q\equiv1 \pmod 4,p\equiv 3\pmod 8$
$\implies  2$ is a quadratic non-residue of $p\implies2^q\equiv-1\pmod p$
So, $ord_p2∤q$ and the divisors of $p-1=2q$ are $1,2,q,2q$ 
Now, if $ord_p2\mid 2,p\mid (2^2-1)\implies p=3,q=1$ which we don't consider to be prime.
So, $ord_p2=2q=p-1$
