第 16 章：补充证明：群、阶与欧拉函数计数

第10章已经从幂阶公式解释循环群的阶计数。这里保留一般群中的定义与完整证明，并补上“元素阶整除群阶”的陪集论证。群是概括模乘法的语言；下面先从可逆剩余类说明运算，再引入一般定义。概率符号的严格定义也放在本章末尾，供回查。

16.1 从模乘法进入群的语言

前面已经证明的模逆元、幂的周期与原根，可以用群的语言统一表达。群是带一种运算的集合，运算满足：封闭、结合律、有单位元、每个元素有逆元。若运算还满足交换律，称为交换群。群的阶是元素个数，记为 $|G|$ ；它与某个元素的阶是两种不同的数量。

对 $n\ge2$ ，模 $n$ 的互质剩余类组成

$U_n=(\mathbb Z/n\mathbb Z)^\times =\{[a]_n:\gcd(a,n)=1\}.$

其运算为剩余类乘法。第 13.4 节保证乘积仍互质，所以运算封闭；整数乘法给出结合律与交换律； $[1]_n$ 是单位元；第 13.3 节保证每个元素有逆元，而且逆元也与 $n$ 互质。因此 $U_n$ 是有限交换群， $|U_n|=\varphi(n)$ 。

对质数 $p$ ， $U_p$ 就是全部非零剩余类，阶为 $p-1$ 。第 15 章已经完整证明原根存在，所以某个 $g$ 的幂遍历 $U_p$ 。这就是说

$U_p=\langle g\rangle$

是循环群。这里“循环”表示一个元素的幂生成整个群；它是比“每个元素的幂都有周期”更强的性质。

一般模数不保证循环： $U_8=\{1,3,5,7\}$ 有四个元素，却没有阶为四的元素，因而任何单个元素都无法生成全群。

16.2 有限群中的元素阶与循环子群

以下暂用 $1_G$ 表示群单位元。对有限群中的元素 $a$ ，它的阶是满足 $a^d=1_G$ 的最小正整数 $d$ 。

先说明这个正整数一定存在。若 $|G|=N$ ， $1_G,a,a^2,\ldots,a^N$ 共 $N+1$ 项，必有两项相同。设 $a^i=a^j$ 、 $i<j$ ，乘以 $a^{-i}$ 得 $a^{j-i}=1_G$ 。由良序原理可以取最小正指数。

与第 4.2 节同样作带余除法，可以证明对 $k\ge0$ ，

$a^k=1_G\quad\Longleftrightarrow\quad d\mid k.$

因此 $1_G,a,\ldots,a^{d-1}$ 两两不同，且任何非负整数幂都等于其中某一项。这个集合记为 $H=\langle a\rangle$ 。它包含单位元；两项乘积仍是一个幂； $a^j$ 的逆元为 $a^{d-j}$ ，经指数取余仍在集合中。因此 $H$ 是 $G$ 的子群，恰有 $d$ 个元素。

在一般群中也可以使用整数次幂，负次幂由逆元定义；这里的计数只用非负代表。

16.3 陪集划分与拉格朗日定理的完整证明

设 $H$ 是有限群 $G$ 的子群。对 $g\in G$ ，左陪集定义为

$gH=\{gh:h\in H\}.$

第一，每个陪集与 $H$ 等大。 映射 $h\mapsto gh$ 是双射，逆映射为 $x\mapsto g^{-1}x$ ，故 $|gH|=|H|$ 。

第二，两个陪集相交就相同。 若 $z=g_1h_1=g_2h_2$ ，其中 $h_1,h_2\in H$ ，则

$g_2^{-1}g_1=h_2h_1^{-1}\in H.$

记此元素为 $h_0$ ，有 $g_1=g_2h_0$ 。对子群内的 $h$ ， $h_0h\in H$ ，所以 $g_1H\subseteq g_2H$ ；反用 $h_0^{-1}\in H$ 得反向包含。故两个陪集完全相同。

第三，陪集覆盖全群。 每个 $g\in G$ 都属于 $gH$ ，因为 $g=g1_G$ 。

综上，不同左陪集将 $G$ 划分成若干互不重叠、每份恰有 $|H|$ 个元素的集合。若有 $k$ 个不同陪集，则

$|G|=k|H|,\qquad\boxed{|H|\mid|G|}.$

这就是拉格朗日定理。取 $H=\langle a\rangle$ ，便得

$\boxed{\operatorname{ord}(a)\mid|G|}.$

证明没有使用交换律，适用于任意有限群。

整除条件不保证每个因数都实现为元素阶。 例如 $U_8$ 的阶为 $4$ ，其元素阶分别为 $1,2,2,2$ ，没有阶为 $4$ 的元素。后面按每个因数精确计数，依赖的是循环群这一额外条件。

16.4 循环群中的幂阶公式，包括零指数

设 $G=\langle g\rangle$ ， $|G|=N$ ，即 $g$ 的阶为 $N$ 。每个元素唯一写为 $g^k$ ，其中 $0\le k<N$ 。第 14.1 节的论证在群中原样成立：对 $k\ge0$ ，

$\boxed{\operatorname{ord}(g^k)=\frac{N}{\gcd(N,k)}}.$

若 $k>0$ ，写 $N=cn'$ 、 $k=ck'$ ， $c=\gcd(N,k)$ 。对正整数 $m$ ，

$(g^k)^m=1_G \Longleftrightarrow N\mid km \Longleftrightarrow n'\mid k'm \Longleftrightarrow n'\mid m.$

最后一步用 $\gcd(n',k')=1$ 与互质消去律。因此最小正 $m$ 为 $n'=N/c$ 。

若 $k=0$ ， $g^0=1_G$ 的阶为 $1$ ，而 $\gcd(N,0)=N$ ，公式同样给出 $1$ 。这一步补足了概率计数必须包含单位元的边界。

16.5 为什么阶为 d 的元素恰好有欧拉函数那么多个

设 $d\mid N$ ，令 $s=N/d$ 。由刚才的公式，

$\operatorname{ord}(g^k)=d \Longleftrightarrow\gcd(N,k)=s.$

右边要求 $s\mid k$ ，写 $k=st$ 。由于 $0\le k<N=sd$ ，恰有 $0\le t<d$ 。并且

$\gcd(N,k)=\gcd(sd,st)=s\gcd(d,t).$

这个等式也可由第 13.9 节的质数指数逐项取最小值证明。因此

$\operatorname{ord}(g^k)=d \Longleftrightarrow \begin{cases} k=(N/d)t,\\ 0\le t<d,\\ \gcd(t,d)=1. \end{cases}$

当 $d>1$ ，这样的 $t$ 恰有 $\varphi(d)$ 个，因为 $0$ 不互质，统计范围与 $1,\ldots,d$ 等价；当 $d=1$ ，只有 $t=0$ ，且 $\gcd(0,1)=1$ ，也与 $\varphi(1)=1$ 一致。每个 $t$ 对应不同的 $g^k$ ，所以

$\boxed{\#\{x\in G:\operatorname{ord}(x)=d\}=\varphi(d)}.$

若 $d\nmid N$ ，由拉格朗日定理个数为 $0$ 。由计数结果可见，在循环群中每个正因数确实都被实现。

取 $N=2^\alpha$ ，各元素阶只能为 $2^t$ ， $0\le t\le\alpha$ 。其数量为

$\begin{cases} 1,&t=0,\\ 2^{t-1},&1\le t\le\alpha. \end{cases}$

因为 $t\ge1$ 时模 $2^t$ 的互质代表恰为奇数，有一半。总数检查为 $1+\sum_{t=1}^\alpha2^{t-1}=2^\alpha$ ；没有遗漏其他阶。这就是第 10 章到达时间分布中的计数依据。

16.6 原根存在性的另一条证明：所有阶的最小公倍数

新增对话给出另一种证明，可以与第 14.4 节的逐个质数幂构造对照。设 $p>2$ ，令

$E=\operatorname{lcm}\{\operatorname{ord}_p(a):a\in U_p\}.$

每个阶均整除 $p-1$ ，故 $E\mid(p-1)$ 。另一方面，每个非零剩余类都满足 $a^E=1$ 。多项式 $x^E-1$ 因而至少有 $p-1$ 个根；由第 14.3 节的根数上界， $p-1\le E$ 。于是 $E=p-1$ 。

还需要说明有元素的阶恰好达到 $E$ 。写 $E=\prod_i\ell_i^{c_i}$ 。由于是有限多个阶的最小公倍数，对于每个最大质数幂 $\ell_i^{c_i}$ ，存在某个 $a_i$ ，其阶为 $\ell_i^{c_i}t_i$ ，且 $\gcd(\ell_i,t_i)=1$ 。取 $b_i=a_i^{t_i}$ ，幂阶公式给出阶为 $\ell_i^{c_i}$ 。这些阶两两互质，模乘法可交换，第 14.2 节给出 $g=\prod_i b_i$ 的阶为 $E=p-1$ 。故 $g$ 是原根。 $p=2$ 单独取 $g=1$ 即可。

这段“最小公倍数可以由一个元素的阶达到”的构造对有限交换群成立，不能去掉交换条件。例如三元素置换群 $S_3$ 的元素由恒等、换位和三循环组成，阶分别为 $1,2,3$ ，最小公倍数为 $6$ ，却没有阶为 $6$ 的元素。

16.7 样本空间、事件与随机变量

本篇只需要有限概率，不需要先学习连续分布或测度论。设有限样本空间 $\Omega$ 的每个结果 $\omega$ 有概率 $p_\omega\ge0$ ，并满足 $\sum_{\omega\in\Omega}p_\omega=1$ 。事件是其中一个子集 $A$ ，其概率为 $P(A)=\sum_{\omega\in A}p_\omega$ 。互不相交事件的概率可以相加。