## Existence of Primitive Roots

Recall from Section 2.1.2 that the order of an element in a finite group is the smallest  such that . In this section, we prove that is cyclic by using the results of Section 2.5.1 to produce an element of of order  for each prime power divisor  of , and then we multiply these together to obtain an element of order .

We will use the following lemma to assemble elements of each order dividing to produce an element of order .

Lemma 2.5   Suppose have orders  and  , respectively, and that . Then has order .

Proof. This is a general fact about commuting elements of any group; our proof only uses that and nothing special about . Since

the order of is a divisor of . Write this divisor as where and . Raise both sides of the equation

to the power to obtain

Since , we have

so . Since , it follows that . Similarly , so the order of is .

Theorem 2.5 (Primitive Roots)   There is a primitive root modulo any prime  . In particular, the group is cyclic.

Proof. The theorem is true if , since is a primitive root, so we may assume . Write as a product of distinct prime powers :

By Proposition 2.5.5, the polynomial has exactly roots, and the polynomial has exactly roots. There are elements such that but ; each of these elements has order . Thus for each , we can choose an of order . Then, using Lemma 2.5.7 repeatedly, we see that

has order , so  is a primitive root modulo  .

Example 2.5   We illustrate the proof of Theorem 2.5.8 when . We have

The polynomial has roots and has roots , so we may take . The polynomial has roots , and we set . Then is a primitive root. To verify this, note that the successive powers of  are

Example 2.5   Theorem 2.5.8 is false if, e.g.,  is replaced by a power of  bigger than  . For example, the four elements of each have order dividing  , but .

Theorem 2.5 (Primitive Roots mod )   Let  be a power of an odd prime. Then there is a primitive root modulo  .

The proof is left as Exercise 2.28.

Proposition 2.5 (Number of primitive roots)   If there is a primitive root modulo  , then there are exactly primitive roots modulo  .

Proof. The primitive roots modulo  are the generators of , which by assumption is cyclic of order  . Thus they are in bijection with the generators of any cyclic group of order . In particular, the number of primitive roots modulo  is the same as the number of elements of with additive order . An element of has additive order if and only if it is coprime to . There are such elements, as claimed.

Example 2.5   For example, there are primitive roots mod , namely . The primitive roots modulo  are and . There are no primitive roots modulo  , even though .

William 2007-06-01