# 3.7 Primitive Roots

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.

# Proposition

Let  be a primitive root for the prime 

1. Let  be an integer. Then  if and only if 

2. If  and  are integers, then  if and only if 

3. 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