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 .