L07a 群:一个集合配一种运算,守四条规矩
从模 11 的乘法讲起,逐条过群的四条公理,用 Z₁₁* 的乘法表查逆元,再学会判断一个集合配一种运算是不是群。
一句话版
群就是一个集合配一种运算,满足四条规矩:算完不出圈、括号随便加、有一个「什么都不做」的元素、每一步都能撤销。这一讲从头到尾围着一个例子转:1 到 10 这十个数,配上「相乘再除以 11 取余」。
这一页只讲「群」这个定义本身。循环群和生成元在下一页 L07a-2,子群在 L07a-3,判定生成元的定理在 L07b。
先认识这几个词
| 词 | 全称 / 读法 | 一句人话 |
|---|---|---|
| mod 11 | modulo 11,读「模 11」 | 除以 11 只留余数 |
| 群 | group | 一个集合配一种运算,满足四条规矩 |
| Z₁₁* | 读「Z 十一星」 | 1 到 10 这十个数,配上「相乘再 mod 11」 |
| 单位元 | identity element | 和谁运算都不改变对方,乘法里是 1,加法里是 0 |
| 逆元 a⁻¹ | inverse,读「a 的逆」 | 和 a 运算后得到单位元的那个元素 |
| 乘法表 | operation table | 把集合里任意两个数的运算结果排成一张方表 |
| Z | integers | 全体整数:…, −2, −1, 0, 1, 2, … |
一个类比:一套只用一个按钮的积木规则
想象一盒积木,盒子里只有十块,编号 1 到 10。规则只有一条:任意拿两块拼在一起,按「相乘再除以 11 取余」换成盒子里的另一块。
这套规则好用,是因为它守住了四件事。拼出来的东西永远还在盒子里,不会多出第 11 块。三块连着拼,先拼哪两块结果都一样。盒子里有一块 1,拼到谁身上谁都不变。每一块都有一块「搭档」,两块一拼就回到 1,等于什么也没做。
数学家把守住这四件事的「盒子 + 规则」叫做群。换一个盒子、换一条规则,只要四件事都守住,就还是群。
类比在哪里失效:
- 积木拼完就没了,群里的元素用完还在,可以反复参与运算。
- 类比里只有一个盒子。真题会换成整数、换成加法或减法,要重新逐条检查,不能凭印象。
- 「搭档」在乘法里叫逆元,在加法里是相反数,类比没区分这两种写法。
从零讲起
1. 先补一块:模 11 的乘法(补充)
它解决什么问题
普通乘法一路乘下去,数会越来越大。7 × 8 已经是两位数,再乘几次就停不下来。
密码学要的是一个有限的集合,算多少次都还在里面。「乘完除以 11 只留余数」就是这样一个办法:不管乘出多大的数,留下来的余数一定在 0 到 10 之间。
从哪来(补充)
现代的模运算是高斯在 1801 年出版的《算术研究》(Disquisitiones Arithmeticae)里系统建立的。日常最常见的模运算是 12 小时制的钟:10 点再过 5 小时是 3 点,因为 15 除以 12 余 3。
出处:Wikipedia: Modular arithmetic
直觉
把 0 到 10 排成一个 11 格的钟面。从 0 出发往前数,数满 11 格就绕回 0。数到哪一格停,那一格就是余数。
这样一来,再大的数都能落在钟面的某一格上。乘法也一样:先照常相乘,再把乘积放到钟面上数一遍。
一步一步看
目标:在模 11 钟面上数 56 格,看出绕完 5 圈停在 1,这就是 7 × 8 ≡ 1。
-
先照常相乘:7 × 8 = 56。
-
从 0 出发在钟面上往前数 56 格。数到 11、22、33、44、55 时各绕回一次 0,一共绕了 5 圈。
-
55 之后还剩 1 格,停在 1。
-
写成算式就是 56 = 5 × 11 + 1,记作 7 × 8 ≡ 1 (mod 11),读作「7 乘 8 模 11 同余 1」。
怎么算
a × b mod 11 = (a × b) 除以 11 的余数
意思是:先照常算乘积,再看它比 11 的某个倍数多出几,多出来的那个数就是答案。
算余数的笨办法是从乘积里一次次减 11,直到剩下的数小于 11。快一点的办法是先找最接近的 11 的倍数:56 最接近的是 55 = 5 × 11,所以余 1。
常见误解
以为 ≡ 就是等号
7 × 8 ≡ 1 (mod 11) 说的是「56 和 1 除以 11 的余数相同」,56 本身不等于 1。后面括号里的 mod 11 不能省,换成 mod 10,56 的余数就是 6。
试一下
算 3 × 4 mod 11、5 × 9 mod 11、10 × 10 mod 11。
3 × 4 = 12 = 11 + 1,余 1。5 × 9 = 45 = 44 + 1,余 1。10 × 10 = 100 = 99 + 1,余 1。
三道题结果都是 1,下面讲逆元时会再碰到它们。
2. 群的四条公理
它解决什么问题
密码算法要在一个集合里反复做同一种运算,还要能把运算撤销(加密之后能解密)。如果算着算着跑出了集合,或者有的元素撤销不了,整套方案就散了。
群把「能放心反复运算」需要的条件列成四条。四条都满足,后面所有关于生成元、子群的结论才站得住。
从哪来(补充)
「群」(groupe)这个词是伽罗瓦在 1830 年代先用的,他研究的是方程的根互相置换时的对称性。1854 年凯莱的论文给出了有限群的第一个抽象定义,从那以后,群就不再只属于方程,任何满足四条规矩的「集合 + 运算」都算。
出处:Wikipedia: Group (mathematics)
直觉
四条公理各自防一种出事的情况:
- 封闭:防止算出集合以外的东西。
- 结合:防止「先算哪两个」影响结果。
- 单位元:保证有一个「原地不动」的选项。
- 逆元:保证每一步都能撤销。
一步一步看
目标:拿 Z₁₁* 配乘法模 11 逐条过四条公理,看出它为什么每条都满足。
拿 Z₁₁* = {1, 2, …, 10} 配「相乘再 mod 11」逐条过一遍。
-
封闭:随便挑两个,比如 3 × 4 = 12 ≡ 1。1 还在 1 到 10 里。11 是素数,1 到 10 里两个数的乘积不可能是 11 的倍数,余数不会是 0,所以任何两个相乘都不会跑出去。
-
结合:(2 × 3) × 4 = 6 × 4 = 24 ≡ 2;2 × (3 × 4) = 2 × 12 ≡ 2 × 1 = 2。整数乘法本来就满足结合律,取余不影响。
-
单位元:a × 1 = a,所以单位元是 1。
-
逆元:3 × 4 ≡ 1,所以 3 的逆元是 4。每个 a 都和 11 互素,所以都能找到一个乘起来得 1 的搭档。
-
四条全部满足,所以 (Z₁₁*, × mod 11) 是群。
怎么算
群 (G, *) 的四条公理:
- 封闭:对任意 a, b ∈ G,a * b ∈ G
- 结合:(a * b) * c = a * (b * c)
- 单位元:存在 e,使所有 a 有 e * a = a * e = a
- 逆元:每个 a 都有 b,使 a * b = b * a = e,b 记作 a⁻¹
意思是:G 是一个集合,* 是一种运算(可以是乘法、加法,也可以是别的)。四条必须同时满足,少一条就不是群。
课件没有要求交换律 a * b = b * a。这一讲出现的例子都满足交换律,所以暂时不用区分。
常见误解
以为单位元永远是 1
单位元看运算。乘法里是 1,因为乘 1 不变;加法里是 0,因为加 0 不变。整数配加法时,a 的逆元是 −a,因为 a + (−a) = 0。
以为只检查一两个例子就能说「封闭」
封闭要求任意两个元素运算都留在集合里。举一个例子只能说明「这一对没出事」,要下结论得给出理由(例如 11 是素数)或者把整张表算出来。
试一下
整数配减法 (Z, −) 是不是群?找出不满足的那一条。
不是。减法不满足结合律:(5 − 3) − 1 = 1,5 − (3 − 1) = 3,两边不相等。找到一条不满足就够了,不用再查别的。
3. 乘法表与逆元
它解决什么问题
逆元的定义是「乘起来等于 1 的那个数」。对 Z₁₁* 这种只有十个元素的群,最直接的办法是把所有乘积列成一张表,要找谁的逆元,在表里找 1 就行。
从哪来(补充)
这种把群里任意两个元素的运算结果排成方表的做法,叫凯莱表,以 Arthur Cayley 命名,最早出现在他 1854 年的论文《论群的理论》里。群的凯莱表有一个性质:每一行、每一列都把全体元素各用一次。
直觉
表的第 a 行第 b 列写 a × b mod 11。看一整行,就是「a 乘遍所有数」的结果。
在第 a 行里找到 1,它所在的那一列 b 满足 a × b ≡ 1,b 就是 a 的逆元。
一步一步看
目标:在 Z₁₁* 的乘法表里逐行找 1,看出每行恰好有一个 1,逆元可以直接从表上读出来。
-
先看第 3 行:3 × 1 到 3 × 10,各自 mod 11,依次是 3、6、9、1、4、7、10、2、5、8。十个数各出现一次,没有重复。
-
在第 3 行里找 1。它在第 4 列:3 × 4 = 12 ≡ 1。所以 3⁻¹ = 4。
-
反过来看第 4 行,1 落在第 3 列,所以 4⁻¹ = 3。3 和 4 互为逆元。
-
最后一行 a = 10 是 10、9、8、…、1,正好倒过来。因为 10 ≡ −1,乘 10 就是取相反数。
怎么算
a⁻¹ = 第 a 行里 1 所在的那一列
意思是:逆元不用解方程,查表就行。表是对称的(乘法满足交换律),所以第 a 列里 1 所在的行也一样。
负指数照这个规则展开:a⁻² = (a⁻¹)²,也等于 (a²)⁻¹。例如 3⁻² = 4² = 16 ≡ 5;3² = 9,9 × 5 = 45 ≡ 1,所以 (3²)⁻¹ 也是 5。两种算法结果相同,考试可以用一种算、另一种验。
常见误解
把逆元当成倒数 1/a
在 Z₁₁* 里没有分数。3 的逆元是 4,意思是 3 × 4 除以 11 余 1,和 1/3 没有关系。
手画的表有重复也照用
群的乘法表每行每列都是 1 到 10 的一个排列。画完一行发现有数字重复或缺失,说明算错了,先回去改。这也是检查自己算得对不对最快的办法。
试一下
在 Z₁₁* 里求 5⁻¹、7⁻¹ 和 2⁻³。
5 × 9 = 45 ≡ 1,所以 5⁻¹ = 9。7 × 8 = 56 ≡ 1,所以 7⁻¹ = 8。
2⁻³ = (2³)⁻¹ = 8⁻¹。8 × 7 = 56 ≡ 1,所以 2⁻³ = 7。
4. 判断一个集合配一种运算是不是群
它解决什么问题
考试最常见的题型是「X 在运算 Y 下是不是群,为什么」。答题就是把四条公理逐条拿来检查,答「是」要四条都写,答「不是」只要指出一条不满足的。
直觉
四条公理里,最容易出事的是封闭和逆元。结合律在加法、乘法里几乎总成立,单位元也容易找。所以先盯住两件事:算完会不会跑出集合?每个元素能不能撤销?
一步一步看
目标:拿三组集合和运算逐条核对四条公理,看各自卡在哪一条,换成与 10 互素的数后又怎样恢复成群。
拿三个例子各走一遍。
-
(Z, +):两个整数相加还是整数,封闭;加法结合;单位元 0;a 的逆元是 −a。四条都满足,是群。
-
(Z, ×):封闭、结合都满足,单位元是 1。但 2 的乘法逆元要是 1/2,不是整数。逆元这条不满足,不是群。
-
{1, 2, …, 9} 配「相乘再 mod 10」:2 × 5 = 10 ≡ 0,0 不在集合里,封闭不满足。再看 2 那一行,2、4、6、8、0、2、4、6、8,一个 1 都没有,2 也没有逆元。
-
把模 10 的集合换成和 10 互素的数 {1, 3, 7, 9},封闭和逆元都恢复了:3 × 7 = 21 ≡ 1,9 × 9 = 81 ≡ 1。
怎么判断
逐条问四个问题,按这个顺序:
- 两个元素运算完,还在集合里吗?(封闭)
- 加括号的位置换一下,结果变不变?(结合)
- 有没有一个元素,和谁运算都不改变对方?(单位元)
- 每个元素都有搭档吗,运算后回到单位元?(逆元)
任何一问答「否」,就不是群,并写出反例。四问都答「是」,才是群。
常见误解
以为 Zₙ* 总是 {1, …, n − 1}
只在 n 是素数时成立。n 是合数时,要取 1 到 n − 1 里和 n 互素的那些数。n = 10 时就是 {1, 3, 7, 9}。这一讲后面只用素数模数 11 和 7,所以写成 {1, …, n − 1} 没出错。
以为同一个集合要么是群要么不是
是不是群要看运算。整数配加法是群,配乘法不是。题目给的集合一样,运算不一样,答案就不一样,答题第一步先看清运算。
试一下
偶数集合 {…, −4, −2, 0, 2, 4, …} 配普通加法是不是群?
是。两个偶数相加还是偶数,封闭;加法结合;单位元 0 是偶数;偶数 a 的相反数 −a 也是偶数。
奇数集合配普通加法是不是群?
不是。3 + 5 = 8 是偶数,封闭不满足。另外单位元 0 也不在奇数集合里。
把它们串起来
这一页的四个概念是一条线。模运算给出一个有限的集合和一种在里面打转的乘法。群的四条公理规定这种「集合 + 运算」要守哪些规矩。乘法表把所有运算结果一次摆出来,逆元一查就有。判断题就是拿四条公理挨个对照。
Z₁₁* 是贯穿全讲的例子。它是群,单位元 1,逆元成对出现:2 和 6、3 和 4、5 和 9、7 和 8,1 和 10 各自是自己的逆元。
判断题有两个固定陷阱。一个是运算:同样是整数,配加法是群,配乘法不是。另一个是模数:模数是素数时 1 到 n − 1 全部可用,模数是合数时要剔掉和 n 有公因数的数。
下一页 L07a-2 不再看两个不同的数相乘,改看一个数自己反复相乘会走到哪里,这就是循环群。
课件里的坑
- p.5 把 Zₙ* 写成 {1, …, n − 1},只在 n 是素数时成立;一般应取与 n 互素的元素。n = 10 时 2 × 5 ≡ 0,集合不封闭。
- p.9 和 p.26 是同一个集合 Z 配两种运算,一个是群一个不是,答题先看清运算再逐条检查。
- p.4 的定义没有要求交换律。本讲的例子都满足交换律,别把它当成第五条公理写进答案。
- p.8 的 3⁻² 和 (3²)⁻¹ 答案都是 5,这是任何群里都成立的规律,不是巧合。
课后 10 分钟:考点复习
这 10 分钟怎么用:先默写必背,再合上页面把 Z₁₁* 的第 2、5、7 行自己算一遍(每格乘完 mod 11),在每行里找到 1;然后做课件例题和变式题。
必背
- 群的四条公理:封闭、结合、单位元、逆元;判断「是不是群」就逐条检查,找到一条不满足即可
- (Z, +) 是群,单位元 0、逆元 −a;(Z, ×) 不是群,2 没有整数逆元
- Zₙ* 写成 {1, …, n − 1} 只在 n 是素数时成立,一般应取与 n 互素的元素
- 乘法表每行每列都是 1…10 的排列,每行 1 所在的列就是该行的逆元
- Z₁₁* 在乘法 mod 11 下是群,单位元 1;4⁻¹ = 3,6⁻¹ = 2,3⁻² = (3²)⁻¹ = 5
课件例题
例 1(课件 p.6):(Z₁₁*, × mod 11) 的单位元
题面:Z₁₁* = {1, 2, …, 10},运算是乘法再 mod 11,它构成一个群。单位元是什么?逐条说明四条公理成立。
提示
单位元是「乘上去不改变对方」的那个数。封闭和逆元都要用到 11 是素数。
解答
单位元是 1,任何 a 乘 1 再 mod 11 还是 a。
封闭:11 是素数,1 到 10 里两个数的乘积不可能是 11 的倍数,mod 11 后不会是 0,结果还在 1 到 10 里。结合:整数乘法本来就满足结合律,取余不影响。逆元:每个 a 都和 11 互素,所以都有模逆。
例 2(课件 p.7–8):从乘法表查逆元
见下方完整例题。
例 3(课件 p.9):Exercise-1,(Z, +) 是群吗
题面:Z 是全体整数,运算是普通加法。(Z, +) 是不是群?说明理由。
提示
加法里「什么都不做」的数是几?a 加上什么回到它?
解答
是。封闭:两个整数相加还是整数。结合:(a + b) + c = a + (b + c)。单位元是 0,a + 0 = a。a 的逆元是 −a,a + (−a) = 0。
加法群的单位元是 0、逆元是相反数,乘法群是 1 和倒数式的搭档,两套记号别混。
例 4(课件 p.26):Exercise-4,(Z, ×) 是群吗
题面:Z 是全体整数,运算是普通乘法。(Z, ×) 是不是群?说明理由。
提示
先找单位元,再看 2 能不能找到一个整数搭档。
解答
不是。封闭、结合满足,单位元 1 也存在,但逆元不满足:2 的乘法逆元要是 1/2,不是整数;0 也没有逆元。找出一个没有逆元的元素就足够下结论。
完整例题
题面(课件 p.7–8):课件给出 Z₁₁* 的 10 × 10 乘法表,第 a 行第 b 列是 a × b mod 11。用这张表填出 4⁻¹、3⁻¹、6⁻¹、2⁻¹、3⁻²、(3²)⁻¹。
约定:逆元 a⁻¹ 满足 a × a⁻¹ ≡ 1 (mod 11);a⁻² 指 (a⁻¹)²。
解法:
- 4⁻¹:第 4 行里 1 在第 3 列,4 × 3 = 12 ≡ 1,所以 4⁻¹ = 3。
- 3⁻¹:第 3 行里 1 在第 4 列,3⁻¹ = 4。和上一题互为逆元。
- 6⁻¹:第 6 行里 1 在第 2 列,6 × 2 = 12 ≡ 1,所以 6⁻¹ = 2。
- 2⁻¹:同上,2⁻¹ = 6。
- 3⁻²:(3⁻¹)² = 4² = 16 ≡ 5。
- (3²)⁻¹:3² = 9,第 9 行里 1 在第 5 列,9 × 5 = 45 ≡ 1,所以 (3²)⁻¹ = 5。
| 题 | 答案 | 查法 |
|---|---|---|
| 4⁻¹ | 3 | 4 × 3 = 12 ≡ 1 |
| 3⁻¹ | 4 | 同上,互为逆元 |
| 6⁻¹ | 2 | 6 × 2 = 12 ≡ 1 |
| 2⁻¹ | 6 | 同上 |
| 3⁻² | 5 | (3⁻¹)² = 4² = 16 ≡ 5 |
| (3²)⁻¹ | 5 | 3² = 9,9 × 5 = 45 ≡ 1 |
要点:最后两题答案相同,(3²)⁻¹ = (3⁻¹)² 在任何群里都成立。
答题格式:每题写「答案 + 一行验算」,验算就是把两个数相乘再 mod 11,得到 1。
变式题(先自己做)
(1) 整数配减法 (Z, −) 是不是群?说明理由。 (2) Z₁₀* 能不能写成 {1, …, 9}?正确的 Z₁₀* 是什么? (3) 在 Z₁₁* 里求 5⁻¹、7⁻¹ 和 2⁻³。
提示
(1) 拿三个具体的数试结合律。(2) 找两个相乘得 10 的数。(3) 2⁻³ 先算 2³,再找它的逆元。
判分点与答案(非官方评分标准)
判分点:① 「不是群」必须给出具体反例;② 逆元必须带一行验算。
(1) 不是。减法不满足结合律:(5 − 3) − 1 = 1,5 − (3 − 1) = 3。
(2) 不能,2 × 5 ≡ 0,不封闭,2 也没有逆元。正确的是与 10 互素的 {1, 3, 7, 9}。
(3) 5⁻¹ = 9(5 × 9 = 45 ≡ 1);7⁻¹ = 8(7 × 8 = 56 ≡ 1);2⁻³ = (2³)⁻¹ = 8⁻¹ = 7。
闪卡自测
1. 群的四条公理是什么?
封闭、结合、单位元、逆元(p.4)。
2. Z₁₁* 的单位元是什么?(Z, +) 呢?
Z₁₁* 是 1;(Z, +) 是 0(p.6、p.9)。
3. 在 Z₁₁* 里 4⁻¹、6⁻¹、3⁻² 各是多少?
3、2、5(p.8)。
4. 怎么从乘法表里读出逆元?
在第 a 行找 1,它所在的那一列就是 a⁻¹(p.7)。
5. (Z, ×) 为什么不是群?
逆元不满足,2 的乘法逆元 1/2 不是整数(p.26)。
6. Z₁₀* 是什么?为什么不是 {1, …, 9}?
{1, 3, 7, 9};因为 2 × 5 ≡ 0,{1, …, 9} 不封闭(p.5)。
下一讲
下一页 L07a-2 讲循环群:只拿一个元素反复自乘,看它能不能走遍整个 Z₁₁*。复习时先把这一页的乘法表第 4 行和第 7 行默写熟,下一页就是从它们出发。
个人整理的学习笔记,不是官方材料;数字与结论以课件和讲师为准。