## What are primitive roots?

Let p be a prime. Then b is a primitive root for p if the powers of b,
1, b, b^2, b^3, ...
include all of the residue classes mod p (except 0).

Since there are p-1 residue classes mod p (not counting 0), that means the the first p-1 powers of b have to be different mod p.

We have noticed that the powers of b form a repeating cycle, and that cycle can't be longer than p-1 (because of Fermat's Little Theorem). So, b is a primitive root if the cycle is as long as it can possibly be.

Examples: If p=7, then 3 is a primitive root for p because the powers of 3 are 1, 3, 2, 6, 4, 5---that is, every number mod 7 occurs except 0. But 2 isn't a primitive root because the powers of 2 are 1, 2, 4, 1, 2, 4, 1, 2, 4...missing several values.

Example: If p=13, then 2 is a primitive root because the powers of 2 are
1, 2, 4, 8, 3, 6, 12, 11, 9, 5, 10, 7---which is all of the classes mod 13 except 0. There are other primitive roots for 13.

Theorem: If p is a prime, then there is a primitive root for p.
(In fact, if p is a prime and p>2, there are always at least two primitive roots, and sometimes many more.)
The proof of this theorem is hard. It's in our text (9.2?) and in second-semeter abstract algebra.

How to find a primitive root for p? Just try possibilities, starting with 2, 3, ..., until you find one that works.