第 8 章 · 代数结构:群

代数结构研究「带运算的集合」:在一个集合上定义运算,要求它满足若干公理,然后只靠公理推理出一切性质。这样做的好处是「一次证明,处处适用」:整数加法、时钟算术、魔方旋转、密码学的椭圆曲线,只要满足同样的公理,所有定理自动生效。本章以群(group)为主线——它是 RSA(第 9 章)的数学舞台,也是「对称性」的统一语言。

8.1 从半群到群:公理的阶梯

在集合 S 上定义二元运算 *(a * b ∈ S,封闭性),按满足的公理分档:

结构	公理	例子
半群	结合律:(ab)c = a(bc)	非空字符串拼接
幺半群	+ 单位元 e(∀a, ae = ea = a)	字符串拼接 + 空串
群	+ 逆元(∀a, ∃a⁻¹ 使 a*a⁻¹ = e)	整数加法(0 是 e,−a 是逆)
阿贝尔群(交换群)	+ 交换律 ab = ba	加法、乘法(正有理数)

每个公理都不是白给的:结合律让表达式无括号有意义(abc 唯一);单位元让「无操作」有代表;逆元让「消去」和「解方程」成为可能(群中 ax = b 有唯一解 x = a⁻¹b)。注意常见反例:自然数加法(ℕ, +)是幺半群不是群(没有负数,缺逆元);整数乘法也不是群(2 没有整数逆);(ℤ, ×) 连幺半群都不是?不,是幺半群(1 为单位元),但没有逆元,所以不是群。「减法」不是群运算(不结合:1−(2−3) ≠ (1−2)−3)。

群的第一个定理:单位元唯一(设 e、e' 都是,则 e = e*e' = e'),逆元唯一。证明只有两行,但它示范了「只靠公理推理」的玩法。

8.2 群的三个代表:加法群、时钟、置换

模 n 加法群(ℤₙ, +ₙ):集合 {0, 1, …, n−1},运算「加后取余」(第 1 章的同余关系)。它是最小最形象的群:n = 12 时就是时钟(10 点 + 4 点 = 2 点)。它还是循环群的标本:由一个元素(1)反复自加生成整个群。

置换群(Sₙ):n 个对象的全部重排,运算「先做 A 再做 B」。它是最「非交换」的典型(先穿袜子再穿鞋 ≠ 先鞋后袜),也是魔方、拼图谜题、加密置换的数学。凯莱定理:任何群都同构于某个置换群的子群——「每个群都是重排的剪影」,群论统一性的宣言。

对称群与几何:正三角形的旋转对称(旋转 120°、240°、恒等)构成 3 阶循环群;加上翻转是 6 阶群(S₃)。「一个图形的对称性 = 保持它的变换群」,这个视角统一了代数与几何,晶体学、粒子物理都在用。

8.3 子群与拉格朗日定理:群论的中央定理

子群:群的非空子集自己也是群(只需验证:含 e、对 * 封闭、逆元在集合内)。ℤ₆ 的子群:{0}、{0,2,4}、{0,3}、{0,1,2,3,4,5}(由元素 2、3 生成的循环子群)。

元素的阶:aᵏ = e 的最小正 k。ℤ₆ 里元素 2 的阶是 3(2,4,0)。拉格朗日定理:有限群 G 的子群 H 的阶 |H| 整除 |G|。证明思路:子群的左陪集(aH = {a*h : h∈H})把 G 划分(第 1 章的等价关系!)成若干等大的块,块数 × |H| = |G|。∎

拉格朗日的推论一串:群中元素的阶整除群的阶(ℤ₆ 中不可能有 5 阶元素);素数阶群必是循环群且无真子群;费马小定理(第 9 章)不过是「模 p 乘法群的阶是 p−1,元素阶整除它」的直接推论。一个定理锁三章,这就是代数结构「一次证明处处生效」的复利。

8.4 同态与同构:群之间的相似

群同态 f:G → H 保运算:f(a*b) = f(a) ⋄ f(b)(运算前后的结构关系不变)。同构(双射同态)= 「同一个群的两件外衣」。同构的判定不变量:阶、元素的阶的多重集、是否循环、是否交换。

例:(ℤ₄, +₄) 与复数 {1, i, −1, −i} 在乘法下同构(1↔0, i↔1, −1↔2, −i↔3,各自都是 4 阶循环群)。凯莱定理(8.2)正是「同构于置换群」的推广。同构的工程意义:算法可迁移:在一个群里成立的算法,换个同构的载体照样跑(第 9 章把整数运算搬到椭圆曲线点群,靠的就是这一点)。

8.5 为什么计算机人要学群

三件真实的计算机事务直接建在群上:

• 哈希与校验:/checksum 的模运算、CRC 的多项式环(群的近亲:环);
• 密码学:Diffie-Hellman 密钥交换、ElGamal、椭圆曲线密码(ECC)全在「离散对数难」的循环群里做文章(第 9 章 RSA 则在乘法群);
• 错误校正码:Hamming 码、Reed-Solomon(二维码的纠错)建在有限域(群的加强版:加减乘除都有)上。二维码沾了油污还能扫,就是有限域代数在替你兜底。

常见错误

• 验证群只查结合律。三条公理(结合、单位、逆)逐条查,漏一条(比如逆元是否在集合内)就翻车;ℤₙ 的乘法 ℤₙ = {0..n−1} 对 ×ₙ 不是群(0 无逆,非零元素在 n 合数时也可能无逆),但对加法是群。
• 阶与群阶混淆。元素的阶 ≤ 群的阶(拉格朗日),「6 阶群有 4 阶元」直接判错。
• 同构只验证双射。双射 + 保运算才算;任意双射会破坏结构(第 1 章的「函数 ≠ 关系」再版)。
• 把「非交换」当「不是群」。交换性是附加公理(阿贝尔群),非交换群(置换群)是正经群。

练习

1. 证明:群中 (ab)⁻¹ = b⁻¹a⁻¹(提示:验证「乘起来等于 e」,注意顺序)。
2. 手算:ℤ₇ 的乘法群(去掉 0,集合 {1..6},运算乘后取余)的每个元素的阶,验证「阶整除 6」;指出哪些元素生成整个群(原根)。
3. 动手:写程序枚举 ℤ₆ 的全部子集,判定哪些是子群(验证 e 在、封闭、逆在),对照拉格朗日(子群阶只能是 1、2、3、6)。
4. 思考:魔方的所有状态在「转动复合」下构成一个群(约 4.3×10¹⁹ 个元素)。「打乱 20 步内可还原」(上帝之数)是计算机搜索(群 + 剪枝)的成果。结合本章,解释「群」如何把一个玩具问题变成可计算的问题。