有限素域上的乘法群是循环群

对于任意的素数$p$，集合$\mathbb{Z}_p=\{0,1,2,\dots,p-1\}$在模$p$的加法和乘法之下，构成一个域，这是学过抽象代数或者初等数论的读者都会知道的一个事实。其中，根据域的定义，$\mathbb{Z}_p$首先要在模$p$的加法下成为一个交换群，而且由于$\mathbb{Z}_p$的特殊性，它还是一个循环群，这也是比较平凡的事实。但是，考虑乘法呢？

首先，$0$是没有逆元的，我们考虑乘法，是在$\mathbb{Z}^\cdot _p=\mathbb{Z}_p \verb|\| \{0\}=\{1,2,\dots,p-1\}$上考虑的。如果我说，$\mathbb{Z}^\cdot _p$在模$p$之下的乘法也作成一个循环群，这结论就不是很平凡的了！然而这确实是事实，对于所有的素数$p$均成立。而有了这事实，数论中的一些结论就会相当显然了，比如当$d\mid (p-1)$时，$\mathbb{Z}_p$中的$d$次剩余就只有$\frac{p-1}{d}$个了，这是循环群的基本结论。

在《数学天书中的证明》一书中，有该结论的一个证明，但这个证明是存在性的，而我在另外一本书上也看到过类似的存在性证明，也就是说，似乎流行的证明都是存在性的，它告诉我们$\mathbb{Z}^\cdot _p$是一个循环群，但是没告诉我们怎么找到它的生成元。而事实上，高斯在他的《算术探索》中就给出了一个构造性的证明。（在数论中，本文的结论是“原根”那一章的基本知识。）下面笔者正是要重复高斯的证明，供读者参考。

构造性程序 #

首先，$\mathbb{Z}^\cdot _p$在模$p$之下的乘法作成一个有限群，这对要理解本文的读者来说应当是平凡的，不然的话请读者先完成并熟悉这个证明。既然是有限群，那么每个元素的阶都是有限的，我们只要找到一个$p-1$阶的元素，就可以证明$\mathbb{Z}^\cdot _p$是一个循环群。

办法也不算复杂。首先，在$\mathbb{Z}^\cdot _p$中任意选一个元素$a$，假设它是$|a|=r$阶的，则$r\mid (p-1)$，如果$r=p-1$，那么自然“打完收工”；否则在$\mathbb{Z}_p$中考虑方程$x^{r}=1$，由于$a$是$r$阶的，所以$a^{r}=1$，从而也有
$$1=1^r=a^{r}=(a^2)^{r}=\dots=(a^{r-1})^{r_1}$$
$x^{r}=1$在$\mathbb{Z}_p$中至多有$r$个不同的解，而上式表明$1,a,a^2,\dots,a^{r-1}$正是它的$r$个不同的解，从而是全部解。也就是说，对于每个$d\mid r$，$\mathbb{Z}^\cdot _p$中的$d$阶元素在集合$\{1,a,a^2,\dots,a^{r-1}\}$中。

然后，在$\mathbb{Z}^\cdot _p$中除去这$r$个数，在剩下的元素中选一个$b$，假设它是$|b|=s$阶的，如果$s=p-1$，那么任务完成；否则，由于已经排除了前面$r$个数，因此$s\nmid r$，因此$r,s$的最小公倍数$[r,s] > \max\{r,s\}$，考虑元素$ab$，那么$ab$便是$[a,b]$阶的，如果$[a,b]=p-1$，那么任务完成；否则按照前一步类似的方法，把
$$1,ab,(ab)^2,\dots,(ab)^{[a,b]-1}$$

从$\mathbb{Z}^\cdot _p$中排除掉，在剩下的数中，任意找一个$c$，重复上面的过程。

由于每一步都可以找到比上一步更大的阶的元素，每次找到$d$阶的元素，就删除掉$d$个元素，而$d < p-1$。也就是说，只要没找到$p-1$阶的元素，那么这个程序就不会终结，但是，由于阶有上界$p-1$，那么这个程序必然在有限步内终止。从而必然存在$p-1$阶的元素，所以$\mathbb{Z}^\cdot _p$是循环群，而且上述程序可以帮我们把生成元找出来。

例子展示 #

下面以$p=79$为例子，展示如何找到$\mathbb{Z}^*_{78}$的生成元。第一步，选取$a=2$，必然成立
$$2^{78}\equiv 1 (\bmod\,79)$$
读者或许会说这是费马小定理的结论，但是从代数的角度看，已知$\mathbb{Z}^*_{78}$是群，而上式是有限群的必然结论。现在检验$2^{39}$，发现$2^{39}\equiv 1 (\bmod\,79)$，然后检验$2^3$和$2^{13}$，发现均不模79余1，从而$|2|=39$，计算
$$2^0,2^1,\dots,2^{38}$$
得到

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

发现$3$不在该列表中，故选取$b=3$，不用检验，立马可以判断$6=3\times 2$必然是一个78阶元素（因为每步的阶比原来的高，比39更高的阶只能是78了），所以$6$是$\mathbb{Z}^*_{78}$的一个生成元。

转载到请包括本文地址：https://kexue.fm/archives/3200

更详细的转载事宜请参考：《科学空间FAQ》