对于任意的素数$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$是一个循环群,但是没告诉我们怎么找到它的生成元。而事实上,高斯在他的《算术探索》中就给出了一个构造性的证明。(在数论中,本文的结论是“原根”那一章的基本知识。)下面笔者正是要重复高斯的证明,供读者参考。

阅读剩余部分...