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,q$ be odd primes with $p = 2q + 1$

Show that $2$ is a primitive root modulo $p$ if and only if $q\equiv1\pmod4$

share|cite|improve this question
up vote 4 down vote accepted

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.

share|cite|improve this answer
but $\phi(2q)=2q-2$ ? – user46220 Oct 28 '12 at 18:36
No: $\varphi(2q)=\varphi(2)\varphi(q)=(1)(q-1)$. Or more concretely, how many numbers between $0$ and $2q-1$ are relatively prime to $2q$? Certainly not the even numbers. Just $1$, $3$, and so on to $2q-1$, therefore $q-1$ numbers. – André Nicolas Oct 28 '12 at 18:44
yes sorry my mistake sir. I got confused and assumed $\phi(2)=2$ – user46220 Oct 28 '12 at 19:29
Why do most of the non-residues have to be primitive roots (what makes a non residue also be a prim. root)? – user1685224 May 20 at 6:34
All but one non-residue is, in this case, a primitive root. The argument is given in detail in the answer. For a QR cannot be a primitive root, and there are always $\varphi(p-1)$ primitive roots, wich in this case is $q-1$, while there are $(p-1)/2$ NR, which in this case is $q$. – André Nicolas May 20 at 7:35

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.


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$

share|cite|improve this answer

Your Answer


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

Not the answer you're looking for? Browse other questions tagged or ask your own question.