Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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|improve this question
    
Welcome to math.SE: since you are new, I wanted to let you know a few things about the site. In order to get the best possible answers, it is helpful if you say in what context you encountered the problem, and what your thoughts on it are; this will prevent people from telling you things you already know, and help them give their answers at the right level. If this is homework, please add the homework tag; people will still help, so don't worry. Also, many find the use of imperative ("Prove", "Solve", etc.) to be rude when asking for help; please consider rewriting your post. –  Julian Kuelshammer Oct 27 '12 at 14:51

2 Answers 2

up vote 3 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|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

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$

share|improve this answer

Your Answer

 
discard

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.