第 5 章：原根与循环群的含义

返回目录

5.1 原根为什么能给所有非零余数编号

模质数 $p$ 的非零剩余类共有 $p-1$ 个。若某个 $g$ 的阶恰好为 $p-1$ ，则

$g^0,g^1,\ldots,g^{p-2}$

模 $p$ 互不相同。否则若 $g^i\equiv g^j$ 且 $0\le i<j<p-1$ ，乘 $g^i$ 的逆元就得到 $g^{j-i}\equiv1$ ；而 $0<j-i<p-1$ ，与阶的最小性矛盾。

这 $p-1$ 个不同的非零余数必然遍历全部非零类。这样的 $g$ 称为模 $p$ 的原根。因此每个非零余数 $a$ 都能唯一写为

$a\equiv g^k\pmod p,\qquad0\le k<p-1.$

这里的 $k$ 是 $a$ 在幂循环中的编号。给余数编号，不意味着编号等于余数本身；编号的好处是把乘法转化为指数相加。

5.2 “循环群”是在概括哪件事

把模 $n$ 的全部可逆剩余类记为 $U_n$ ，运算是模 $n$ 乘法。它们满足：乘积仍可逆，有单位元1，每个元素有逆元，乘法满足结合律。具有这些性质的集合称为群；“群的阶”表示它有多少个元素，因此 $|U_n|=\varphi(n)$ 。

如果整个群都能写成某个元素的幂，就称为循环群。于是“模质数 $p$ 的非零剩余类构成 $p-1$ 阶循环群”包含两个结论：它们在乘法下构成群；存在一个原根，能用幂遍历整个群。前一个结论来自逆元与乘法，后一个结论需要证明原根存在，不能混为一件事。

“元素的阶”是回到1所需的最小正指数；“群的阶”是元素总数。它们使用同一个词，但定义不同。有限群中，元素阶整除群阶；第16章用陪集划分证明。对于循环群，我们也可以直接从第4.4节的幂阶公式看出这一点。

5.3 为什么每个质数都有原根

每个质数 $p$ 都存在原根。 $p=2$ 时唯一非零类1就是原根，以下讨论 $p>2$ 。这个结论的关键是：在模质数的运算中，一个非零多项式的根数不超过它的次数。因此，所有非零余数不可能都过早回到1。

具体说，令 $N=p-1$ ，固定 $N$ 的一个质数幂因子 $\ell^e$ ，其中 $\ell^{e+1}$ 不再整除 $N$ 。多项式 $X^{N/\ell}-1$ 的次数是 $N/\ell<N$ ，不可能让全部 $N$ 个非零余数都成为根。因此存在一个余数 $a$ 满足 $a^{N/\ell}\not\equiv1$ 。

$a$ 的阶 $d$ 整除 $N$ ，但不整除 $N/\ell$ 。所以 $d$ 中必须含有完整的因子 $\ell^e$ ；否则它的每个质数幂因子都包含在 $N/\ell$ 里，就会整除 $N/\ell$ 。具体取 $b=a^{d/\ell^e}$ ；幂阶公式给出它的阶为 $d/\gcd(d,d/\ell^e)=\ell^e$ ，因此我们得到一个阶恰为 $\ell^e$ 的元素。