The Structure of $(\mathbb{Z}/p\mathbb{Z}{})^*$

This section is about the structure of the group $(\mathbb{Z}/p\mathbb{Z}{})^*$ of units modulo a prime number $p$ . The main result is that this group is always cyclic. We will use this result later in Chapter 4 in our proof of quadratic reciprocity.

Definition 2.5 (Primitive root)   A primitive root modulo an integer $n$ is an element of $(\mathbb{Z}/n\mathbb{Z}{})^*$ of order $\varphi (n)$ .

We will prove that there is a primitive root modulo every prime $p$ . Since the unit group $(\mathbb{Z}/p\mathbb{Z}{})^*$ has order $p-1$ , this implies that $(\mathbb{Z}/p\mathbb{Z}{})^*$ is a cyclic group, a fact this will be extremely useful, since it completely determines the structure of $(\mathbb{Z}/p\mathbb{Z}{})^*$ as a group.

If $n$ is an odd prime power, then there is a primitive root modulo $n$ (see Exercise 2.28), but there is no primitive root modulo the prime power $2^3$ , and hence none mod $2^n$ for $n\geq 3$ (see Exercise 2.27).

Section 2.5.1 is the key input to our proof that $(\mathbb{Z}/p\mathbb{Z}{})^*$ is cyclic; here we show that for every divisor $d$ of $p-1$ there are exactly $d$ elements of $(\mathbb{Z}/p\mathbb{Z}{})^*$ whose order divides $d$ . We then use this result in Section 2.5.2 to produce an element of $(\mathbb{Z}/p\mathbb{Z}{})^*$ of order $q^r$ when $q^r$ is a prime power that exactly divides $p-1$ (i.e., $q^r$ divides $p-1$ , but $q^{r+1}$ does not divide $p-1$ ), and multiply together these elements to obtain an element of $(\mathbb{Z}/p\mathbb{Z}{})^*$ of order $p-1$ .

SAGE Example 2.5   In SAGE use the primitive_root command to compute the smallest positive integer that is a primitive root modulo $n$ . For example, below we compute primitive roots modulo $p$ for each prime $p<20$ .

sage: for p in primes(20):
...    print p, primitive_root(p)
2 1
3 2
5 2
7 3
11 2
13 2
17 3
19 2