Consider the powers of
Note that we obtain all the nonzero congruence classes mod 7 as powers of 3. This means that 3 is a primitive root mod 7 (the term multiplicative generator might be better but is not as common). Similarly, every nonzero congruence class mod 13 is a power of 2, so 2 is a primitive root mod 13. However, so the powers of 3 mod 13 repeat much more frequently:
so only 1, 3, 9 are powers of 3. Therefore, 3 is not a primitive root mod 13. The primitive roots mod 13 are 2, 6, 7, 11.
In general, when is a prime, a primitive root mod is a number whose powers yield every nonzero class mod It can be shown that there are primitive roots mod In particular, there is always at least one. In practice, it is not difficult to find one, at least if the factorization of is known. See Exercise 54.
The following summarizes the main facts we need about primitive roots.
Let be a primitive root for the prime
Let be an integer. Then if and only if
If and are integers, then if and only if
A number is a primitive root mod if and only if is the smallest positive integer such that
Proof. If then for some Therefore,
by Fermat’s theorem. Conversely, suppose We want to show that divides so we divide into and try to show that the remainder is 0. Write
(this is just division with quotient and remainder ). We have
Suppose If we consider the powers of then we get back to 1 after steps. Then
so the powers of yield only the numbers Since not every number mod can be a power of This contradicts the assumption that is a primitive root.
The only possibility that remains is that This means that so divides This proves part (1).
For part (2), assume that (if not, switch and ). Suppose that Dividing both sides by yields By part (1), so Conversely, if then so again by part (1). Multiplying by yields the result.
For part (3), if is a primitive root, then part (1) says that any integer with must be a multiple of so is the smallest. Conversely, suppose is the smallest. Look at the numbers If two are congruent mod say with then (note: implies that so we can divide by ). Since this contradicts the assumption that is smallest. Therefore, the numbers must be distinct mod Since there are numbers on this list and there are numbers mod the two lists must be the same, up to order. Therefore, each number on the list is congruent to a power of so is a primitive root mod
Warning: is a primitive root mod if and only if is the smallest positive such that If you want to prove that is a primitive root, it does not suffice to prove that After all, Fermat’s theorem says that every satisfies this, as long as To prove that is a primitive root, you must show that is the smallest positive exponent such that