# Quadratic reciprocity and proving a number is a primitive root

Let $p$ and $q$ be odd primes. Show that 2 is a primitive root of $q$, if $q = 4p + 1$

-
I have already shown that 2 is a quadratic nonresidue by applying Euler's Criterion formula –  user39898 Dec 12 '12 at 4:50

$ord_q2\mid \phi(q)$ $\phi(q)=q-1=4p$

So, $ord_q2\mid 4p\implies ord_q2$ can be $2,4,p,2p,4p$

So, $p=2a+1,q=4p+1=4(2a+1)+1\equiv5\pmod 8$

Using this, $2$ is not a quadratic residue of $q\implies 2^{\frac{q-1}2}\equiv-1\pmod q\not\equiv1\implies 2^{2p}\not\equiv1$

So, $ord_q2\not\mid 2p$ so $ord_q2$ can be one of $4,4p$

If $ord_q2=4,q\mid(2^4-1)\implies q=3$ or $5$

But $3$ is not of the form $4p+1,$ and $ord_32=2=\phi(3)\implies 2$ primitive root of $3.$

If $q=5,4=4p=5-1=\phi(5)\implies 2$ is primitive roots of $5.$(here $p=1$ which is not considered to be prime, though)

$\implies ord_q2=4p=\phi(q)$ for $q\ge 5$

-