# Prove that 2 is a primitive root modulo p.

• Mar 21st 2010, 04:17 PM
NikoBellic
Prove that 2 is a primitive root modulo p.
Suppose q is a prime and p=4q+1 is a prime. Prove that 2 is a primitive root modulo p.
• Mar 21st 2010, 05:51 PM
chiph588@
Quote:

Originally Posted by NikoBellic
Suppose q is a prime and p=4q+1 is a prime. Prove that 2 is a primitive root modulo p.

First observe that $\displaystyle 2^{\frac{p-1}{2}}\equiv\pm 1 \mod{p}$.

In this case, $\displaystyle 2$ is a primitive root if and only if $\displaystyle 2^{\frac{p-1}{2}}\equiv -1 \mod{p}$. (Ask if you'd like to see the proof of this.)

Assume otherwise, so $\displaystyle 2^{\frac{p-1}{2}}\equiv 1 \mod{p}$.
Note $\displaystyle \frac{p-1}{2} = 2q$.

Now by Euler's Criterion, $\displaystyle 2^{2q}\equiv 1\mod{p} \iff \left(\frac{2}{p}\right)=1$

$\displaystyle \left(\frac{2}{p}\right)=1 \implies p\equiv 1 \text{ or } 7\mod{8}$. Since $\displaystyle p\equiv 1 \mod{4} \implies p\equiv 1 \text{ or } 5 \mod{8}$. Thus $\displaystyle p\equiv 1\mod{8} \implies 8\mid p-1 \implies 8\mid 4q \implies 2\mid q \implies q=2$, which is a contradiction since $\displaystyle 4\cdot 2+1 =9$ is not prime.

Thus $\displaystyle 2^{\frac{p-1}{2}} \not\equiv 1 \mod{p} \implies 2^{\frac{p-1}{2}}\equiv -1 \mod{p} \implies 2$ is a primitive root modulo $\displaystyle p$.