L07a-3 子群:走不遍全群的元素,绕出一个小群
4 的幂只走到 {1, 3, 4, 5, 9},这五个数在乘法 mod 11 下自己也是群。逐帧补全子群乘法表,看子群为什么也是循环群,再补一条课件没讲的规律:子群大小一定整除群大小。
一句话版
从一个大群里挑出一部分元素,用同一种运算,如果这部分自己也守住群的四条规矩,它就是子群。Z₁₁* 里 4 的幂只走到 1、3、4、5、9,这五个数就是一个子群。
群的四条公理见 L07a,元素的阶和生成元见 L07a-2。这一页只讲子群。
先认识这几个词
| 词 | 全称 / 读法 | 一句人话 |
|---|---|---|
| 子群 | subgroup | 群的一部分,在同一种运算下自己也是群 |
| H | 常用来记子群的字母 | 这一页里 H = {1, 3, 4, 5, 9} |
| 子集 | subset | 从一个集合里挑出的一部分元素 |
| 周期 | period | 幂的结果每几步重复一次,就是元素的阶 |
| M | 课件给的小集合 | M = {1, 10} |
| 整除 | divides | a 整除 b,就是 b 除以 a 没有余数 |
一个类比:大转盘里的小环线
一座城的地铁有十个站,编号 1 到 10。某条线只停其中五个站:1、3、4、5、9。
这条小环线有个特点:从这五个站里任意出发、按规则换乘,下车的地方还是这五个站之一,永远出不了这条线。它有起点站 1,每一站也都能原路返回。所以它自己就是一个完整的小系统,不需要借用另外五个站。
子群就是这样一条「自给自足」的小线路。
类比在哪里失效:
- 真实地铁的小环线要靠人设计。子群是运算自己决定的,你挑哪几个数没用,乘出来跑不出去才算。
- 地铁线路可以有任意多站,子群的大小却受限制:在 Z₁₁* 里只能是 1、2、5、10 个元素,这一页最后一个概念会讲为什么。
从零讲起
1. 子群怎么判
它解决什么问题
上一页看到 4 的幂只走到五个数。这五个数能不能单独当一个群用?要回答这个问题,需要一个判断标准:从群里挑出一部分,什么条件下它自己也是群。
直觉
结合律不用查:运算和原来的群一样,原来满足,挑出一部分照样满足。要查的只有三件事:挑出来的数互相运算有没有跑出去、单位元在不在里面、每个数的逆元在不在里面。
其中最容易漏的是第一件。只要有一对数乘出了圈外,就不是子群。
一步一步看
目标:把 H 的 5 × 5 乘法表逐行补全,再逐条核对四条公理,看 H 是不是 Z₁₁* 的子群。
拿 H = {1, 3, 4, 5, 9} 配「相乘再 mod 11」,把 5 × 5 的乘法表一行一行补全。
-
先填 1 和 3 两行。1 那行照抄列头;3 那行是 3、9、12 ≡ 1、15 ≡ 4、27 ≡ 5。
-
补 4 那一行:4 × 1 = 4,4 × 3 = 12 ≡ 1,4 × 4 = 16 ≡ 5,4 × 5 = 20 ≡ 9,4 × 9 = 36 ≡ 3。五个结果都在 H 里。
-
补 5 和 9 两行:5 那行是 5、15 ≡ 4、20 ≡ 9、25 ≡ 3、45 ≡ 1;9 那行是 9、27 ≡ 5、36 ≡ 3、45 ≡ 1、81 ≡ 4。
-
25 格全是 1、3、4、5、9 之一,封闭成立。
-
单位元 1 在 H 里。每一行都有一个 1:3 和 4 互为逆元,5 和 9 互为逆元,1 是自己的逆元。
-
结合律继承自 Z₁₁* 的乘法。四条都满足,H 是 Z₁₁* 的子群。
怎么判断
子集 H 是群 G 的子群,要同时满足:
- 封闭:H 里任意两个元素运算,结果还在 H 里
- 单位元:G 的单位元在 H 里
- 逆元:H 里每个元素的逆元也在 H 里
结合律从 G 继承,不用再查。
答题时把乘法表画全,逐格确认封闭,再在表里找 1 确认逆元。任何一条不满足,写出那个反例。
常见误解
只验证了单位元和逆元就说是子群
最容易漏的是封闭。{1, 2} 有单位元 1,但 2 × 2 = 4 不在集合里,不封闭,不是子群。2 的逆元 6 也不在里面。
以为课件的表只印了两行,剩下的不用管
课件只给了 1 和 3 两行,4、5、9 三行留空。只看两行没法确认封闭,考试要你说明「为什么是群」时,表要自己补全。
试一下
{1, 3, 9} 在乘法 mod 11 下是不是 Z₁₁* 的子群?
不是。3 × 9 = 27 ≡ 5,5 不在集合里,不封闭。另外 3 的逆元 4 也不在里面。
2. 子群也是循环群
它解决什么问题
H 是由 4 的幂走出来的。反过来问:H 自己是不是循环群?如果是,谁能当它的生成元?这决定了以后在子群里做运算时,能不能照搬上一页「指数 mod q」那一套。
直觉
H 本来就是 4 一路自乘走出来的,所以 4 一定能生成 H。再看 H 里的其他数:它们自乘也跑不出 H(封闭),只要它们走得够久、不提前回到 1,就会把 H 走满。
一步一步看
目标:逐个求 H 里各元素的幂,看出除了 1 以外,每个元素都能生成整个 H。
-
4 的幂:4、5、9、3、1,五个数全走到,H = ⟨4⟩。
-
3 的幂:3¹ = 3,3² = 9,3³ = 9 × 3 = 27 ≡ 5,3⁴ = 5 × 3 = 15 ≡ 4,3⁵ = 4 × 3 = 12 ≡ 1。
-
3 也把 H 的五个数走满了,所以 3 也是 H 的生成元。
-
5 的幂:5、3、4、9、1。9 的幂:9、4、3、5、1。它们也是 H 的生成元。
-
只有 1 不行,1 的幂永远是 1。
怎么判断
在子群 H 里,元素 h 是 H 的生成元,当且仅当 h 的幂恰好走遍 H
意思是:判断方法和上一页一样,只是「群」换成了子群。走满的标准是 H 的元素个数,不是 Z₁₁* 的 10。
所以同一个 3,对 H 是生成元,对 Z₁₁* 不是。
常见误解
以为「3 生成一个子群」和「3 不是生成元」互相矛盾
两句话的对象不同。前者说 3 生成了子群 {1, 3, 4, 5, 9},3 是这个子群的生成元。后者说 3 不是整个 Z₁₁* 的生成元,因为它只走到一半元素。
以为子群一定比原群「简单」,不会是循环群
循环群的子群一定也是循环群。H 是循环群,{1, 10} 也是,{1} 也是(由 1 生成)。
试一下
列出 2 在 mod 7 下的幂,它生成的集合是什么?是 Z₇* 的生成元吗?
2¹ = 2,2² = 4,2³ = 8 ≡ 1。生成 {1, 2, 4},只有 3 个元素。Z₇* 有 6 个元素,所以 2 不是 Z₇* 的生成元,只是这个 3 阶子群的生成元。
3. 子群大小整除群大小(补充)
它解决什么问题
Z₁₁* 有 10 个元素,它的子群能有几个元素?能不能有一个 3 个元素的子群?逐个试太费事。有一条一般规律直接回答这个问题,课件没讲,但拿来检查答案很好用。
从哪来(补充)
这条规律叫拉格朗日定理:有限群的每个子群的元素个数、每个元素的阶,都整除群的元素个数。它以拉格朗日命名,但拉格朗日自己没有证明一般形式,1771 年的论文里只有相关结论。高斯 1801 年证明了模素数乘法群的特例,柯西 1844 年证明了对称群的情形,若尔当 1861 年推广到任意置换群。
出处:Wikipedia: Lagrange’s theorem (group theory)
直觉
一个元素的幂每走若干步回到 1,这个步数就是它的阶,也是它生成的子群的大小。Z₁₁* 里每个元素走 10 步一定回到 1(7¹⁰ ≡ 1 这类事实)。如果它更早回到 1,那么这个更早的步数必须能把 10 整分,否则走到第 10 步时停不在 1 上。
一步一步看
目标:数出 Z₁₁* 里每个元素生成的子群有多大,看出大小只可能是 10 的因数。
-
1 的幂只有 1,生成 {1},1 个元素。
-
10 的幂是 10、1,生成 {1, 10},2 个元素。
-
3、4、5、9 的幂都在 {1, 3, 4, 5, 9} 里打转,5 个元素。
-
2、6、7、8 的幂走满全部 10 个元素。
-
四种大小 1、2、5、10,都是 10 的因数。10 的因数只有这四个,所以不会出现 3 个、4 个或 7 个元素的子群。
怎么算
子群 H 的元素个数 | 群 G 的元素个数
意思是:竖线读作「整除」。子群的元素个数一定能整除原群的元素个数。元素的阶是它生成的子群的大小,所以元素的阶也一定整除群的大小。
在 Z₁₁* 里,10 = 2 × 5,因数是 1、2、5、10,所以每个元素的阶只能是这四个数之一。
常见误解
以为反过来也成立:10 的每个因数都对应一个子群
对循环群来说成立,Z₁₁* 里 1、2、5、10 各有一个子群。但「整除」只是必要条件,换成不是循环群的群,就不一定每个因数都有对应的子群。这一讲只用 Z₁₁*,不会碰到反例。
以为这条规律是课件内容,可以直接写进答案
课件没讲,它是补充。答「是不是子群」时仍要画表、逐条检查;整除关系只用来自查,例如有人说找到了 4 个元素的子群,就一定算错了。
试一下
Z₇* 有 6 个元素。它的子群可能有几个元素?2 生成的 {1, 2, 4} 符合吗?
6 的因数是 1、2、3、6,子群只可能有这几种大小。{1, 2, 4} 有 3 个元素,3 整除 6,符合。
把它们串起来
子群是从大群里挑出的一部分,用同一种运算,自己也守住四条规矩。判断时结合律白送,要查的是封闭、单位元和逆元,其中封闭最容易漏,必须把乘法表画全。
Z₁₁* 的子群都可以由某个元素自乘走出来。4、3、5、9 走出 {1, 3, 4, 5, 9},10 走出 {1, 10},1 只有它自己,2、6、7、8 走满整个群。每个子群自己也是循环群,里面的生成元就是那些能把它走满的元素。
子群的大小不是随意的。它一定整除原群的大小,所以 Z₁₁* 的子群只有 1、2、5、10 个元素四种。这条规律课件没讲,拿来查错很方便。
下一页 L07b 把这些串起来回答一个实际问题:既然元素的阶只有这几种可能,判断谁是生成元时能不能只算一个幂。
课件里的坑
- [读图提醒] p.12 两个例子里的「generator」生成的是子群,不是整个 Z₇* 或 Z₁₁*;和 p.21「3 不是生成元」不矛盾。
- p.15 的 4ⁱ 一行只印了 4¹ = 4,p.16 的子群乘法表只印了 1 和 3 两行,其余要自己填。下面课件例题里的表已全部验算。
- p.17 只问 H 是不是循环群,答「是,H = ⟨4⟩」就够;3、5、9 也是生成元,多写一句更稳。
- p.28 的 M = {1, 10} 里,10 就是 −1,(−1)² = 1,所以 {1, −1} 在任何 Zₚ* 里都是一个 2 阶子群。
课后 10 分钟:考点复习
这 10 分钟怎么用:先默写必背,再合上页面把 H 的 5 × 5 乘法表从头画一遍,在每行里圈出 1;然后做完整例题和变式题。
必背
- 子群 = 一个群的子集,在同一种运算下自己也满足四条公理;判断时最容易漏的是封闭,要把乘法表画全
- 4 的幂周期为 5,生成 {1, 3, 4, 5, 9}
- H = {1, 3, 4, 5, 9} 是 Z₁₁* 的子群,3 ↔ 4、5 ↔ 9 互为逆元;H = ⟨4⟩,3、5、9 也是生成元
- 2 在 mod 7 下生成 3 阶子群 {1, 2, 4},3 在 mod 11 下生成 5 阶子群 {1, 3, 4, 5, 9}
- M = {1, 10} 是群,也是循环群 ⟨10⟩
- 子群的元素个数一定整除原群的元素个数(拉格朗日定理,补充):Z₁₁* 的子群只有 1、2、5、10 个元素四种
课件例题
例 1(课件 p.12):两个 q 阶子群
题面:(1) g = 2、n = 7,求 g 的幂 mod 7 回到 1 的最小次数 q,以及 g 生成的集合;(2) g = 3、n = 11,同样求 q 和生成的集合。
提示
每格用上一格乘 g 再 mod n,第一次出现 1 时停下。
解答
(1) 2¹ ≡ 2,2² ≡ 4,2³ = 8 ≡ 1 (mod 7)。q = 3,生成 {1, 2, 4}。
(2) 3¹ ≡ 3,3² ≡ 9,3³ = 27 ≡ 5,3⁴ ≡ 15 ≡ 4,3⁵ ≡ 12 ≡ 1 (mod 11)。q = 5,生成 {1, 3, 4, 5, 9}。
两个都只跑出一部分元素:Z₇* 有 6 个元素,2 只跑出 3 个;Z₁₁* 有 10 个,3 只跑出 5 个。这里的「生成元」指它生成的子群,不是整个群。
例 2(课件 p.15–16):4 的幂与子群 H
见下方完整例题。
例 3(课件 p.17):Exercise-2,H 是循环群吗
题面:H = {1, 3, 4, 5, 9},运算是乘法 mod 11。H 是不是循环群?
提示
在 H 里挑一个数,看它的幂能不能走满五个数。
解答
是。4 的幂依次是 4, 5, 9, 3, 1,跑遍 H,所以 H = ⟨4⟩。
3、5、9 也都能生成 H:3 的幂是 3, 9, 5, 4, 1;5 的幂是 5, 3, 4, 9, 1;9 的幂是 9, 4, 3, 5, 1。只有 1 不行,它的幂永远是 1。
例 4(课件 p.28):Exercise-6,M = {1, 10} 是群吗、是循环群吗
题面:M = {1, 10},运算是乘法 mod 11。填出 2 × 2 运算表,判断 M 是不是群、是不是循环群。
提示
10 × 10 = 100,100 除以 11 余几?
解答
| × | 1 | 10 |
|---|---|---|
| 1 | 1 | 10 |
| 10 | 10 | 1 |
10 × 10 = 100 = 99 + 1 ≡ 1。表里只有 1 和 10,封闭;结合继承自乘法;单位元 1;1 和 10 都是自己的逆元。所以是群。
也是循环群:10¹ = 10,10² ≡ 1,M = ⟨10⟩。
完整例题
题面(课件 p.15–16):在 Z₁₁* 中把 4¹ 到 4¹⁰ mod 11 填完,说明它的周期;再补全 H = {1, 3, 4, 5, 9} 的乘法表,说明 (H, × mod 11) 为什么是群。
约定:每格用上一格乘 4 再 mod 11;H 的表第 a 行第 b 列是 a × b mod 11。
解法:
- 4 的幂依次是 4, 16 ≡ 5, 20 ≡ 9, 36 ≡ 3, 12 ≡ 1, 4, 5, 9, 3, 1。
- 4⁵ 就回到 1,之后重复,周期是 5,跑出的集合是 {1, 3, 4, 5, 9}。
- 补全 H 的乘法表:
| × | 1 | 3 | 4 | 5 | 9 |
|---|---|---|---|---|---|
| 1 | 1 | 3 | 4 | 5 | 9 |
| 3 | 3 | 9 | 1 | 4 | 5 |
| 4 | 4 | 1 | 5 | 9 | 3 |
| 5 | 5 | 4 | 9 | 3 | 1 |
| 9 | 9 | 5 | 3 | 1 | 4 |
- 封闭:25 格全在 H 里。
- 结合:继承自 Z₁₁* 的乘法。
- 单位元:1 在 H 里。
- 逆元:每行都有 1,3 和 4 互逆,5 和 9 互逆,1 是自己的逆元。所以 H 是 Z₁₁* 的子群。
要点:表必须画全才能说封闭;逆元从每行 1 的位置读出。
答题格式:先写 4 的幂和周期,再画 5 × 5 表,最后按四条公理逐条写一句。
变式题(先自己做)
(1) 列出 5 在 Z₁₁* 里的幂,它生成的子群是什么?5 是 Z₁₁* 的生成元吗? (2) {1, 10} 和 {1, 3, 4, 5, 9} 都是 Z₁₁* 的子群,分别有几个生成元? (3) 自编:{1, 4, 5} 在乘法 mod 11 下是不是子群?
提示
(1) 每格用上一格乘 5 再 mod 11。(2) 逐个元素列幂,看谁能走满。(3) 先查封闭,试 4 × 4。
判分点与答案(非官方评分标准)
判分点:① 幂要逐格写出;② 「不是子群」要给出具体反例。
(1) 5, 25 ≡ 3, 15 ≡ 4, 20 ≡ 9, 45 ≡ 1;生成 H = {1, 3, 4, 5, 9};不是 Z₁₁* 的生成元,阶只有 5。
(2) {1, 10} 只有 10 一个生成元;{1, 3, 4, 5, 9} 有 3、4、5、9 四个。
(3) 不是。4 × 4 = 16 ≡ 5 还在里面,但 4 × 5 = 20 ≡ 9,9 不在集合里,不封闭。另外它有 3 个元素,3 不整除 10,按拉格朗日定理也不可能是子群。
闪卡自测
1. 子群的定义是什么?最容易漏查哪一条?
群的子集,在同一种运算下自己也是群;最容易漏的是封闭(p.16)。
2. 4 在 Z₁₁* 里的周期是多少?生成什么?
周期 5,生成子群 {1, 3, 4, 5, 9}(p.15–16)。
3. H = {1, 3, 4, 5, 9} 是循环群吗?生成元有哪些?
是,H = ⟨4⟩,3、5、9 也是生成元(p.17)。
4. 2 在 mod 7 下生成什么?
3 阶子群 {1, 2, 4}(p.12)。
5. {1, 10} 在乘法 mod 11 下是循环群吗?
是,{1, 10} = ⟨10⟩,因为 10 × 10 = 100 ≡ 1(p.28)。
6. Z₁₁* 的子群可能有几个元素?
1、2、5、10 四种,都是 10 的因数(拉格朗日定理,补充)。
下一讲
下一页 L07b 讲怎么判定生成元:p = 2p₁ + 1 时只算一个幂就够。复习时先把「Z₁₁* 的子群只有 1、2、5、10 个元素」记住,下一页的定理就是从这里推出来的。
个人整理的学习笔记,不是官方材料;数字与结论以课件和讲师为准。