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$
Tell me more
×
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.
|
|
||||
|
|
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. |
|||||||
|
|
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$ |
||||
|
|
