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

Printable View

- Mar 21st 2010, 04:17 PMNikoBellicProve 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 PMchiph588@
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 $.