Suppose q is a prime and p=4q+1 is a prime. Prove that 2 is a primitive root modulo p.
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 .