# Math Help - Prove that 2 is a primitive root modulo p.

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

2. 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 $2^{\frac{p-1}{2}}\equiv\pm 1 \mod{p}$.

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

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

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

$\left(\frac{2}{p}\right)=1 \implies p\equiv 1 \text{ or } 7\mod{8}$. Since $p\equiv 1 \mod{4} \implies p\equiv 1 \text{ or } 5 \mod{8}$. Thus $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 $4\cdot 2+1 =9$ is not prime.

Thus $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 $p$.