Existence of Primitive Roots

Recall from Section 2.1.2 that the order of an element $x$ in a finite group is the smallest $m\geq 1$ such that $x^m=1$ . In this section, we prove that $(\mathbb{Z}/p\mathbb{Z}{})^*$ is cyclic by using the results of Section 2.5.1 to produce an element of $(\mathbb{Z}/p\mathbb{Z}{})^*$ of order $d$ for each prime power divisor $d$ of $p-1$ , and then we multiply these together to obtain an element of order $p-1$ .

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

Lemma 2.5   Suppose $a,b\in(\mathbb{Z}/n\mathbb{Z}{})^*$ have orders $r$ and $s$ , respectively, and that $\gcd(r,s)=1$ . Then $ab$ has order $rs$ .

Proof. This is a general fact about commuting elements of any group; our proof only uses that $ab=ba$ and nothing special about $(\mathbb{Z}/n\mathbb{Z}{})^*$ . Since

$$(ab)^{rs} = a^{rs}b^{rs}=1,$$

the order of $ab$ is a divisor of $rs$ . Write this divisor as $r_1 s_1$ where $r_1\mid r$ and $s_1\mid s$ . Raise both sides of the equation

$$a^{r_1 s_1}b^{r_1 s_1} = (ab)^{r_1 s_1} = 1$$

to the power $r_2 = r/r_1$ to obtain

$$a^{r_1 r_2 s_1} b^{r_1 r_2 s_1} = 1.$$

Since $a^{r_1 r_2 s_1} = (a^{r_1 r_2})^{s_1} = 1$ , we have

$$b^{r_1 r_2 s_1} = 1,$$

so $s\mid r_1 r_2 s_1$ . Since $\gcd(s,r_1 r_2)=\gcd(s,r) = 1$ , it follows that $s=s_1$ . Similarly $r=r_1$ , so the order of $ab$ is $rs$ . $\qedsymbol$

Theorem 2.5 (Primitive Roots)   There is a primitive root modulo any prime $p$ . In particular, the group $(\mathbb{Z}/p\mathbb{Z}{})^*$ is cyclic.

Proof. The theorem is true if $p=2$ , since $1$ is a primitive root, so we may assume $p>2$ . Write $p-1$ as a product of distinct prime powers $q_i^{n_i}$ :

$$p-1 = q_1^{n_1}q_2^{n_2}\cdots q_r^{n_r}.$$

By Proposition 2.5.5, the polynomial $x^{q_i^{n_i}}-1$ has exactly $q_i^{n_i}$ roots, and the polynomial $x^{q_i^{n_i-1}}-1$ has exactly $q_i^{n_i-1}$ roots. There are $q_i^{n_i} - q_i^{n_i-1}=q_i^{n_i-1}(q_i-1)$ elements $a\in\mathbb{Z}/p\mathbb{Z}{}$ such that $a^{q_i^{n_i}}=1$ but $a^{q_i^{n_i-1}}\neq 1$ ; each of these elements has order $q_i^{n_i}$ . Thus for each $i=1,\ldots, r$ , we can choose an $a_i$ of order $q_i^{n_i}$ . Then, using Lemma 2.5.7 repeatedly, we see that

$$a = a_1 a_2 \cdots a_r$$

has order $q_1^{n_1}\cdots q_r^{n_r} = p-1$ , so $a$ is a primitive root modulo $p$ . $\qedsymbol$

Example 2.5   We illustrate the proof of Theorem 2.5.8 when $p=13$ . We have

$$p-1 = 12 = 2^2\cdot 3.$$

The polynomial $x^4 - 1$ has roots $\{1,5,8,12\}$ and $x^2-1$ has roots $\{1,12\}$ , so we may take $a_1=5$ . The polynomial $x^3-1$ has roots $\{1,3,9\}$ , and we set $a_2=3$ . Then $a=5\cdot 3=15\equiv 2$ is a primitive root. To verify this, note that the successive powers of  $2\pmod{13}$ are

$$2, 4, 8, 3, 6, 12, 11, 9, 5, 10, 7, 1.$$

Example 2.5   Theorem 2.5.8 is false if, e.g., $p$ is replaced by a power of $2$ bigger than $4$ . For example, the four elements of $(\mathbb{Z}/8\mathbb{Z}{})^*$ each have order dividing $2$ , but $\varphi (8)=4$ .

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

The proof is left as Exercise 2.28.

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

Proof. The primitive roots modulo $n$ are the generators of $(\mathbb{Z}/n\mathbb{Z}{})^*$ , which by assumption is cyclic of order  $\varphi (n)$ . Thus they are in bijection with the generators of any cyclic group of order $\varphi (n)$ . In particular, the number of primitive roots modulo $n$ is the same as the number of elements of $\mathbb{Z}/\varphi (n)\mathbb{Z}{}$ with additive order $\varphi (n)$ . An element of $\mathbb{Z}/\varphi (n)\mathbb{Z}{}$ has additive order $\varphi (n)$ if and only if it is coprime to $\varphi (n)$ . There are $\varphi (\varphi (n))$ such elements, as claimed. $\qedsymbol$

Example 2.5   For example, there are $\varphi (\varphi (17)) = \varphi (16)=2^4-2^3=8$ primitive roots mod $17$ , namely $3, 5, 6, 7, 10, 11, 12, 14$ . The $\varphi (\varphi (9)) = \varphi (6) = 2$ primitive roots modulo $9$ are $2$ and $5$ . There are no primitive roots modulo $8$ , even though $\varphi (\varphi (8)) = \varphi (4) = 2>0$ .