Let $p$ and $q$ be odd primes. Show that 2 is a primitive root of $q$, if $q = 4p + 1$
Quadratic reciprocity and proving a number is a primitive root
3
$\begingroup$
number-theory
quadratic-reciprocity
-
0I have already shown that 2 is a quadratic nonresidue by applying Euler's Criterion $f$ormula – 2012-12-12
1 Answers
4
$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$