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

Printable View

- March 21st 2010, 05: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.

- March 21st 2010, 06:51 PMchiph588@
First observe that .

In this case, is a primitive root if and only if . (Ask if you'd like to see the proof of this.)

Assume otherwise, so .

Note .

Now by Euler's Criterion,

. Since . Thus , which is a contradiction since is not prime.

Thus is a primitive root modulo .