The Multiplicative Group of a Finite Prime Field is Cyclic

有限素域上的乘法群是循环群 苏剑林 · 2015-01-20 · Mathematics prime number group theory field

For any prime $p$, the set $\mathbb{Z}_p=\{0,1,2,\dots,p-1\}$, under addition and multiplication modulo $p$, forms a field—this is a fact that anyone who has studied abstract algebra or elementary number theory will know. According to the definition of a field, $\mathbb{Z}_p$ must first be an abelian group under addition modulo $p$, and moreover, because of the special nature of $\mathbb{Z}_p$, it is also a cyclic group—this too is a fairly trivial fact. But what about multiplication?

First of all, $0$ has no multiplicative inverse, so when we consider multiplication, we're really considering it on $\mathbb{Z}^\cdot _p=\mathbb{Z}_p \verb|\| \{0\}=\{1,2,\dots,p-1\}$. If I told you that $\mathbb{Z}^\cdot _p$ under multiplication modulo $p$ also forms a cyclic group, this conclusion would not be so trivial! Yet it is indeed true, for every prime $p$. And once we have this fact, some conclusions in number theory become quite obvious—for instance, when $d\mid (p-1)$, the number of $d$-th power residues in $\mathbb{Z}_p$ is exactly $\frac{p-1}{d}$, which is a basic consequence of the theory of cyclic groups.

In Proofs from the Book, there is a proof of this result, but it's an existence proof; I've also seen a similar existence-style proof in another book. It seems that the popular proofs are all of the existence type—they tell us that $\mathbb{Z}^\cdot _p$ is cyclic, but they don't tell us how to actually find a generator. In fact, Gauss, in his Disquisitiones Arithmeticae, gave a constructive proof. (In number theory, the result of this post is basic material from the chapter on "primitive roots.") Below, I'll reproduce Gauss's proof for the reader's reference. more

A Constructive Procedure

First, $\mathbb{Z}^\cdot _p$ under multiplication modulo $p$ forms a finite group—this should be trivial for readers trying to follow this post; if not, please first work through and become familiar with that proof. Since it's a finite group, every element has finite order, and to prove that $\mathbb{Z}^\cdot _p$ is cyclic, we just need to find an element of order $p-1$.

The method isn't too complicated. First, pick an arbitrary element $a$ in $\mathbb{Z}^\cdot _p$, and suppose it has order $|a|=r$, so that $r\mid (p-1)$. If $r=p-1$, then we're done, mission accomplished; otherwise, consider the equation $x^{r}=1$ in $\mathbb{Z}_p$. Since $a$ has order $r$, we have $a^{r}=1$, and hence also

$$1=1^r=a^{r}=(a^2)^{r}=\dots=(a^{r-1})^{r_1}$$

$x^{r}=1$ has at most $r$ distinct solutions in $\mathbb{Z}_p$, and the equation above shows that $1,a,a^2,\dots,a^{r-1}$ are exactly $r$ distinct solutions of it, and thus constitute all of them. In other words, for every $d\mid r$, any element of order $d$ in $\mathbb{Z}^\cdot _p$ must lie in the set $\{1,a,a^2,\dots,a^{r-1}\}$.

Next, remove these $r$ numbers from $\mathbb{Z}^\cdot _p$, and from the remaining elements pick one, $b$, and suppose it has order $|b|=s$. If $s=p-1$, the task is complete; otherwise, since the previous $r$ numbers have already been excluded, we have $s\nmid r$, and so if $[r,s] > \max\{r,s\}$ is the least common multiple of $r,s$, consider the element $ab$: then $ab$ has order $[a,b]$. If $[a,b]=p-1$, the task is complete; otherwise, following the same method as in the previous step, exclude

$$1,ab,(ab)^2,\dots,(ab)^{[a,b]-1}$$

from $\mathbb{Z}^\cdot _p$, and from the numbers that remain, pick an arbitrary $c$ and repeat the process above.

Since at each step we can find an element with order larger than the previous step's, and each time we find an element of order $d$ we remove $d$ elements, while $d < p-1$—that is, so long as we haven't found an element of order $p-1$, the procedure won't terminate. But since the order is bounded above by $p-1$, this procedure must terminate within finitely many steps. Hence there must exist an element of order $p-1$, so $\mathbb{Z}^\cdot _p$ is cyclic, and moreover the procedure above helps us actually find the generator.

An Example

Let's take $p=79$ as an example, and show how to find a generator of $\mathbb{Z}^*_{78}$. In the first step, choose $a=2$; it must hold that

$$2^{78}\equiv 1 (\bmod\,79)$$

You might say this is just a consequence of Fermat's little theorem, but from an algebraic point of view, given that $\mathbb{Z}^*_{78}$ is a group, the equation above is simply a necessary consequence of being a finite group. Now check $2^{39}$, and find that $2^{39}\equiv 1 (\bmod\,79)$; then check $2^3$ and $2^{13}$, and find that neither is congruent to 1 modulo 79. Hence $|2|=39$. Compute

$$2^0,2^1,\dots,2^{38}$$

to get

1, 2, 4, 8, 16, 32, 64, 49, 19, 38, 76, 73, 67, 55, 31, 62, 45, 11, 22, 44, 9, 18, 36, 72, 65, 51, 23, 46, 13, 26, 52, 25, 50, 21, 42, 5, 10, 20, 40

We find that $3$ is not in this list, so we choose $b=3$. No further checking is needed—we can immediately conclude that $6=3\times 2$ must be an element of order 78 (since the order at each step is higher than before, and the only order higher than 39 available is 78). So $6$ is a generator of $\mathbb{Z}^*_{78}$.