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

-

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.

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

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

-