For any prime p, the set \mathbb{Z}_p = \{0, 1, 2, \dots, p-1\} forms a field under addition and multiplication modulo p. 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. But what if we consider multiplication?
First, 0 does not have a multiplicative inverse. We consider multiplication on the set \mathbb{Z}_p^* = \mathbb{Z}_p \setminus \{0\} = \{1, 2, \dots, p-1\}. If I say that \mathbb{Z}_p^* also forms a cyclic group under multiplication modulo p, this conclusion is not quite trivial! However, it is indeed a fact that holds for all primes p. With this fact, several conclusions 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; this is a fundamental conclusion regarding cyclic groups.
In the book Proofs from THE BOOK, there is a proof of this conclusion, but it is existential. I have also seen similar existential proofs in other books. That is to say, it seems that popular proofs are mostly existential; they tell us that \mathbb{Z}_p^* is a cyclic group, but they 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 is basic knowledge in the chapter on “primitive roots.”) Below, I will repeat Gauss’s proof for the reader’s reference.
Constructive Procedure
First, the fact that \mathbb{Z}_p^* forms a finite group under multiplication modulo p should be trivial for readers intended for this article; otherwise, please first complete and familiarize yourself with that proof. Since it is a finite group, the order of every element is finite. We only need to find an element of order p-1 to prove that \mathbb{Z}_p^* is a cyclic group.
The method is not overly complex. First, arbitrarily choose an element a in \mathbb{Z}_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 thus: 1 = 1^r = a^r = (a^2)^r = \dots = (a^{r-1})^r The equation x^r = 1 has at most r distinct solutions in \mathbb{Z}_p, and the above expression shows that 1, a, a^2, \dots, a^{r-1} are precisely its r distinct solutions, and therefore all of its solutions. That is to say, for every d \mid r, any element of order d in \mathbb{Z}_p^* must be in the set \{1, a, a^2, \dots, a^{r-1}\}.
Next, exclude these r numbers from \mathbb{Z}_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 we have already excluded the previous r numbers, s \nmid r. Therefore, the least common multiple of r and s, denoted [r, s], satisfies [r, s] > \max\{r, s\}. Consider the element ab; then ab is of order [r, s]. If [r, s] = p-1, the task is complete; otherwise, following a method similar to the previous step, exclude 1, ab, (ab)^2, \dots, (ab)^{[r, s]-1} from \mathbb{Z}_p^*, and find any element c among the remaining numbers, repeating the process above.
Since each step finds an element of a larger order than the previous step, and each time we find an element of order d, we delete 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. Consequently, an element of order p-1 must exist, so \mathbb{Z}_p^* is a cyclic group, and the above procedure helps us find the generator.
Example Demonstration
Below, we take p=79 as an example to demonstrate how to find a generator for \mathbb{Z}_{79}^*. In the first step, select a=2. It must hold 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 for a finite group, given that \mathbb{Z}_{79}^* is a group. Now check 2^{39}; we find 2^{39} \equiv 1 \pmod{79}. Then check 2^3 and 2^{13}, and find that neither is congruent to 1 modulo 79. Thus |2|=39. Calculating 2^0, 2^1, \dots, 2^{38} we obtain:
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 select b=3. Without further testing, we can immediately judge that 6 = 3 \times 2 must be an element of order 78 (because the order in each step is higher than the previous, and the only order higher than 39 can only be 78). Therefore, 6 is a generator of \mathbb{Z}_{79}^*.
When reposting, please include the original address of this article: https://kexue.fm/archives/3200
For more detailed reposting matters, please refer to: Scientific Space FAQ