← COMP5521 全部讲次
L07a · 第 8 周

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。

  1. 先照常相乘:7 × 8 = 56。

  2. 从 0 出发在钟面上往前数 56 格。数到 11、22、33、44、55 时各绕回一次 0,一共绕了 5 圈。

  3. 55 之后还剩 1 格,停在 1。

    模 11 的钟面:0 到 10 排成一圈,右边逐行写 7 乘 8 等于 56、从 0 数 56 格、每 11 格绕一圈、绕了 5 圈、还剩 1 格,最后一行 56 等于 5 乘 11 加 1,余数是 1;钟面上的 1 用青绿圈出

  4. 写成算式就是 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」逐条过一遍。

  1. 封闭:随便挑两个,比如 3 × 4 = 12 ≡ 1。1 还在 1 到 10 里。11 是素数,1 到 10 里两个数的乘积不可能是 11 的倍数,余数不会是 0,所以任何两个相乘都不会跑出去。

  2. 结合:(2 × 3) × 4 = 6 × 4 = 24 ≡ 2;2 × (3 × 4) = 2 × 12 ≡ 2 × 1 = 2。整数乘法本来就满足结合律,取余不影响。

  3. 单位元:a × 1 = a,所以单位元是 1。

  4. 逆元:3 × 4 ≡ 1,所以 3 的逆元是 4。每个 a 都和 11 互素,所以都能找到一个乘起来得 1 的搭档。

    四个面板逐条检查 Z₁₁*:封闭面板写 3 乘 4 等于 12 同余 1,结果还在 1 到 10 里;结合面板写两种加括号都得 2;单位元面板写 a 乘 1 等于 a;逆元面板写 3 乘 4 同余 1。底部青绿字:四条全部满足,所以是群

  5. 四条全部满足,所以 (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 年的论文《论群的理论》里。群的凯莱表有一个性质:每一行、每一列都把全体元素各用一次。

出处:Wikipedia: Cayley table

直觉

表的第 a 行第 b 列写 a × b mod 11。看一整行,就是「a 乘遍所有数」的结果。

在第 a 行里找到 1,它所在的那一列 b 满足 a × b ≡ 1,b 就是 a 的逆元。

一步一步看

目标:在 Z₁₁* 的乘法表里逐行找 1,看出每行恰好有一个 1,逆元可以直接从表上读出来。

  1. 先看第 3 行:3 × 1 到 3 × 10,各自 mod 11,依次是 3、6、9、1、4、7、10、2、5、8。十个数各出现一次,没有重复。

    Z₁₁* 的 10 乘 10 乘法表,第 a 行第 b 列是 a 乘 b 模 11。第 3 行加了浅底并用黑字显示:3、6、9、1、4、7、10、2、5、8,其他行是灰字

  2. 在第 3 行里找 1。它在第 4 列:3 × 4 = 12 ≡ 1。所以 3⁻¹ = 4。

    同一张乘法表,第 3 行第 4 列的 1 用青绿圈出,列头的 4 也是青绿色,标题写第 3 行里 1 落在第 4 列,副标题写 3 乘 4 等于 12 同余 1,所以 3 的逆元是 4

  3. 反过来看第 4 行,1 落在第 3 列,所以 4⁻¹ = 3。3 和 4 互为逆元。

  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 互素的数后又怎样恢复成群。

拿三个例子各走一遍。

  1. (Z, +):两个整数相加还是整数,封闭;加法结合;单位元 0;a 的逆元是 −a。四条都满足,是群。

  2. (Z, ×):封闭、结合都满足,单位元是 1。但 2 的乘法逆元要是 1/2,不是整数。逆元这条不满足,不是群。

  3. {1, 2, …, 9} 配「相乘再 mod 10」:2 × 5 = 10 ≡ 0,0 不在集合里,封闭不满足。再看 2 那一行,2、4、6、8、0、2、4、6、8,一个 1 都没有,2 也没有逆元。

    模 10 的乘法表只画 2 和 5 两行,列是 1 到 9。2 那一行是 2、4、6、8、0、2、4、6、8,没有 1;2 乘 5 那一格的 0 用青绿圈出。底部写合数模数时只留和 n 互素的数,Z₁₀* 等于 1、3、7、9

  4. 把模 10 的集合换成和 10 互素的数 {1, 3, 7, 9},封闭和逆元都恢复了:3 × 7 = 21 ≡ 1,9 × 9 = 81 ≡ 1。

怎么判断

逐条问四个问题,按这个顺序:

  1. 两个元素运算完,还在集合里吗?(封闭)
  2. 加括号的位置换一下,结果变不变?(结合)
  3. 有没有一个元素,和谁运算都不改变对方?(单位元)
  4. 每个元素都有搭档吗,运算后回到单位元?(逆元)

任何一问答「否」,就不是群,并写出反例。四问都答「是」,才是群。

常见误解

以为 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;然后做课件例题和变式题。

必背

  1. 群的四条公理:封闭、结合、单位元、逆元;判断「是不是群」就逐条检查,找到一条不满足即可
  2. (Z, +) 是群,单位元 0、逆元 −a;(Z, ×) 不是群,2 没有整数逆元
  3. Zₙ* 写成 {1, …, n − 1} 只在 n 是素数时成立,一般应取与 n 互素的元素
  4. 乘法表每行每列都是 1…10 的排列,每行 1 所在的列就是该行的逆元
  5. 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²)⁻¹。

Z₁₁* 的完整 10 × 10 乘法表,表头行列都是 1 到 10,第 a 行第 b 列是 a × b mod 11。例如第 2 行是 2 4 6 8 10 1 3 5 7 9,第 10 行是 10 9 8 7 6 5 4 3 2 1;每一行每一列 1 到 10 各出现一次
图片来源:COMP5521 Lecture_7-Cyclic Group.pdf, p.7

约定:逆元 a⁻¹ 满足 a × a⁻¹ ≡ 1 (mod 11);a⁻² 指 (a⁻¹)²。

解法:

  1. 4⁻¹:第 4 行里 1 在第 3 列,4 × 3 = 12 ≡ 1,所以 4⁻¹ = 3。
  2. 3⁻¹:第 3 行里 1 在第 4 列,3⁻¹ = 4。和上一题互为逆元。
  3. 6⁻¹:第 6 行里 1 在第 2 列,6 × 2 = 12 ≡ 1,所以 6⁻¹ = 2。
  4. 2⁻¹:同上,2⁻¹ = 6。
  5. 3⁻²:(3⁻¹)² = 4² = 16 ≡ 5。
  6. (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 行默写熟,下一页就是从它们出发。

下一讲 →
L07a-2 L07a-2 循环群:一个元素自乘就能走遍全群

个人整理的学习笔记,不是官方材料;数字与结论以课件和讲师为准。