By 苏剑林 | January 20, 2015
For any prime number $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 known to any reader who has studied abstract algebra or elementary number theory. According to the definition of a field, $\mathbb{Z}_p$ must first be an abelian group under addition modulo $p$. Furthermore, due to the specific nature of $\mathbb{Z}_p$, it is also a cyclic group, which is a relatively trivial fact. However, what about multiplication?
First, $0$ has no inverse, so we consider multiplication on the set $\mathbb{Z}^\cdot_p = \mathbb{Z}_p \setminus \{0\} = \{1,2,\dots,p-1\}$. If I say that $\mathbb{Z}^\cdot_p$ also forms a cyclic group under multiplication modulo $p$, this conclusion is not quite so trivial! Yet it is indeed a fact, and it holds for all prime numbers $p$. With this fact, several results in number theory become quite obvious. For instance, when $d \mid (p-1)$, there are exactly $\frac{p-1}{d}$ $d$-th power residues in $\mathbb{Z}_p$, which is a fundamental conclusion regarding cyclic groups.
In the book Proofs from THE BOOK, there is a proof of this conclusion, but that proof is existential. I have seen similar existential proofs in other books as well. In other words, it seems that popular proofs tend to be existential; they tell us that $\mathbb{Z}^\cdot_p$ is a cyclic group but do not tell us how to find its generator. In fact, Gauss provided a constructive proof in his Disquisitiones Arithmeticae. (In number theory, the conclusion of this article represents the fundamental knowledge in the chapter on "primitive roots.") Below, I will replicate Gauss's proof for the reader's reference.
Constructive Procedure
First, it should be trivial for readers understanding this article that $\mathbb{Z}^\cdot_p$ forms a finite group under multiplication modulo $p$; if not, please finish and familiarize yourself with that proof first. Since it is a finite group, every element has a finite order. We only need to find an element of order $p-1$ to prove that $\mathbb{Z}^\cdot_p$ is a cyclic group.
The method is not overly complex. First, arbitrarily choose an element $a \in \mathbb{Z}^\cdot_p$. Suppose its order is $\|a\|=r$, then $r \mid (p-1)$. If $r=p-1$, then the work is naturally finished. Otherwise, consider the equation $x^r=1$ in $\mathbb{Z}_p$. Since $a$ is of order $r$, we have $a^r=1$, and consequently:
$$1=1^r=a^r=(a^2)^r=\dots=(a^{r-1})^r=1$$
The equation $x^r=1$ has at most $r$ distinct solutions in $\mathbb{Z}_p$, and the expression above shows that $1, a, a^2, \dots, a^{r-1}$ are exactly its $r$ distinct solutions, and thus all of its solutions. This means that for every $d \mid r$, any element of order $d$ in $\mathbb{Z}^\cdot_p$ must be in the set $\{1, a, a^2, \dots, a^{r-1}\}$.
Next, exclude these $r$ numbers from $\mathbb{Z}^\cdot_p$ and choose an element $b$ from the remaining elements. Suppose its order is $\|b\|=s$. If $s=p-1$, the task is complete. Otherwise, since the previous $r$ numbers have been excluded, $s \nmid r$. Consequently, the least common multiple $[r,s] > \max\{r,s\}$. Consider the element $ab$. Then $ab$ has an order related to $[a,b]$. [Note: If $\gcd(r,s)=1$, the order is exactly $rs$. In general, one can construct an element of order $\text{lcm}(r,s)$ from elements of order $r$ and $s$]. If we reach an element of order $p-1$, the task is finished; otherwise, following a method similar to the previous step, exclude:
$$1, ab, (ab)^2, \dots, (ab)^{[a,b]-1}$$
from $\mathbb{Z}^\cdot_p$, find an arbitrary element $c$ from the remaining numbers, and repeat the process.
Because each step allows us to find an element of higher order than the previous step, and each time we find an element of order $d$, we remove $d$ elements where $d < p-1$. That is to say, as long as an element of order $p-1$ has not been found, the procedure will not terminate. However, since the order has an upper bound of $p-1$, the procedure must terminate within a finite number of steps. Thus, an element of order $p-1$ must necessarily exist. Therefore, $\mathbb{Z}^\cdot_p$ is a cyclic group, and the above procedure helps us find the generator.
Example Demonstration
Taking $p=79$ as an example, let us demonstrate how to find a generator for $\mathbb{Z}^*_{78}$ [Note: implying the group of order 78]. In the first step, choose $a=2$. It necessarily holds that:
$$2^{78} \equiv 1 \pmod{79}$$
Readers might say this is a conclusion of Fermat's Little Theorem, but from an algebraic perspective, it is a necessary conclusion of a finite group given that $\mathbb{Z}^*_{78}$ is a group. Now check $2^{39}$; we find $2^{39} \equiv 1 \pmod{79}$. Then check $2^3$ and $2^{13}$, finding neither is congruent to 1 modulo 79. Thus $\|2\|=39$. Calculate:
$$2^0, 2^1, \dots, 2^{38} \pmod{79}$$
This yields:
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$. Without further checking, one can immediately judge that $6=3 \times 2$ must be an element of order 78 (because the order in each step is higher than before, and the only order higher than 39 can only be 78). Therefore, $6$ is a generator of $\mathbb{Z}^*_{78}$.
Original address: https://kexue.fm/archives/3200
,
author={Su Jianlin},
year={2015},
month={Jan},
url={\url{https://kexue.fm/archives/3200}},
}