Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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

share|cite|improve this question
I have already shown that 2 is a quadratic nonresidue by applying Euler's Criterion formula – user39898 Dec 12 '12 at 4:50
up vote 3 down vote accepted

$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$

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.