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

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

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

构造性程序

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

办法也不算复杂。首先,在$\mathbb{Z}^*_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}^*_p$中的$d$阶元素在集合$\{1,a,a^2,\dots,a^{r-1}\}$中。

然后,在$\mathbb{Z}^*_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}^*_p$中排除掉,在剩下的数中,任意找一个$c$,重复上面的过程。

由于每一步都可以找到比上一步更大的阶的元素,每次找到$d$阶的元素,就删除掉$d$个元素,而$d < p-1$。也就是说,只要没找到$p-1$阶的元素,那么这个程序就不会终结,但是,由于阶有上界$p-1$,那么这个程序必然在有限步内终止。从而必然存在$p-1$阶的元素,所以$\mathbb{Z}^*_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}$的一个生成元。


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

如果您觉得本文还不错,欢迎点击下面的按钮对博主进行打赏。打赏并非要从中获得收益,而是希望知道科学空间获得了多少读者的真心关注。当然,如果你无视它,也不会影响你的阅读。再次表示欢迎和感谢!