群(离散数学).ppt

1、离 散 数 学,2020年9月22日星期二,2020/9/22,第十三章 群,2020/9/22,12.1 本章学习要求,2020/9/22,13.2半群与含幺半群,定义13.2.1 在二元代数中，若二元运算“”满足结合律，则称为半群；特别地，若半群中的二元运算“”满足交换律，则称为可交换半群。 定义13.2.2 设为半群，若S中存在关于运算“”的幺元e，则称此半群为独异点（或含幺半群），有时也记为； 若独异点中运算“”满足交换律，则称为可交换独异点（可交换含幺半群）。,2020/9/22,例13.2.1,设A是非空集合，AA表示所有A到A的函数集合，运算“”表示映射的复合运算，证明是半群。

2、分析 只需证明运算“”满足封闭性和结合律。 证明 对f, gAA， 显然有fgAA， 故封闭性成立。又函数复合运算“”满足结合律，所以是半群。,2020/9/22,例13.2.2,设S是一个集合，P(S)是S的幂集合，试证明代数系统 与都是可交换的含幺半群。 分析 运算“”和“”显然满足交换律，因此只需说明 与是半群，并计算它们的幺元即可。,2020/9/22,例13.2.2（续）,证明 显然运算“”和“”均满足结合律和交换律，因此它们是可交换的半群。 易证和S分别是 和的幺元。因此， 与是可交换的含幺半群。,2020/9/22,例13.2.3,设n0, 1, 2, , n1, 定义n上的运算

3、n 如下： x, yn, xnyxy (mod n) (即xy除以n的余数)。 证明是含么半群。 证明：封闭性：x, yn, 令kxy (mod n), 则 0kn1, 即kn, 所以封闭性成立；,2020/9/22,例13.2.3（续）,结合律：x, y, zn, 有 (xn y)n zxy+z (mod n)xn (yn z) 所以结合律成立。 单位元：xn, 显然有 0nxxn0=x 所以0是单位元。故是含么半群。,2020/9/22,子半群和子含幺半群,将子代数应用于半群，可得下面的定义： 定义13.2.3 如果是半群，T是S的非空子集，且运算“” 对T封闭，则称是半群的子半群； 如果

4、是含幺半群，T是S的非空子集，eT。且运算“”对T封闭，则称是含幺半群的子含幺半群。,2020/9/22,例13.2.4,设是含幺半群， M = a | aS，xS 有ax = xa， 则 是的子含幺半群。 分析 需证明两点：幺元存在，运算“” 封闭。 证明 (1) 设e是半群的幺元，则xS，显然有 e x = x e， 因此，eM。进而M是S的非空子集。,2020/9/22,例13.2.4（续）,（2）对任意a, bM，由M的定义知，xS，有 a x = x a， b x = x b， 又运算“*”满足结合律，则 (a b) x = a (b x) = a (x b) = (a x) b =

5、 (x a) b = x (a b)， 即 xS, (a b) x = x (a b)， 因此，(ab) M。 由(1)、(2)可知：是的一个子含幺半群。,2020/9/22,13.2.2 元素的幂,设S, *是一个半群, 对x S, 可定义： x=x, x=x x, x=x x= x x=x x x, xn=xn-1 x=x xn -=x x x x。 如果S, *有单位元e, 可以定义：x0=e,2020/9/22,元素的幂（续）,由于结合律的满足, 同样有 如下的公式： ax ay=ax+ y (a)=a,2020/9/22,例13.2.6,（1）设是半群，aS， M = an | nZ

6、+， 则是的子半群； （2）设是含幺半群，aS， M = an | nN， 则是的子含幺半群； 分析 （1）M是非空子集，运算“” 封闭。 （2）还需说明幺元e在M中。,2020/9/22,例13.2.6（续）,证明 （1）a = a1M，所以M是非空集合。 对nZ+，anS，因此M是S的非空子集。 对an，amM，n，mZ+，则 anam = an+m， n + mZ+， anamM。 故运算“” 封闭。是的子半群。 （2）幺元e = a0M，即幺元在M中。类似（1），同理可证是的子含幺半群。,2020/9/22,13.2.3 循环半群,定义13.2.4 （1）在半群中，若存在一个元素aS，

7、使得对任意xS，都有 x = an，其中nZ+， 则称为循环半群，并称a为该循环半群的一个生成元，M = a | (aS)且a是S的生成元称为该循环半群的生成集；,2020/9/22,定义13.2.4（续）,（2）在含幺半群中，若存在一个元素aS，使得对任意xS，都有 x = an，其中nN， 则称此循环含幺半群为循环含幺半群（或循环独异点），并称a为该循环含幺半群的一个生成元，M = a | (aS)且a是S的生成元称为该循含幺半群的生成集。,2020/9/22,例13.2.7,判断含幺半群是否是一个循环含幺半群？ 分析 根据定义，判别含幺半群（或半群）是循环含幺半群（循环半群）的关键是计算

8、生成元。 如何计算生成元呢？ 首先假设生成元存在，然后根据定义得到方程，通过解这个方程来计算生成元。,2020/9/22,例13.2.7（续）,如在本例中，不妨假设aN是的生成元，则根据生成元的定义，对nN，mN，使得 n = am = ma 让n = 1，有1 = ma，因此a = 1。这说明，如果有生成元，则生成元必须为1。下面还需验证1是生成元。,2020/9/22,例13.2.7（续）,解 由于存在元素1N，使得对任意nN，都有： n = (n1)+1 = 1+（n1） = 1+1+1+1 = 1n， 特别对幺元0N，有0 = 10。 所以，“1”是生成元。 因此，该半群一定是循环含幺

9、半群。,2020/9/22,定理13.2.1,循环半群都是可交换半群。 分析 由于循环半群中的每个元素都可以表示为生成元的方幂形式，可以使用这种表示形式来证明。 证明 设aS是循环半群的生成元。则对x, yS，存在m, nZ+，使得 x = am，y = an，所以 x y = am an = am+n = an+m = an am = y x， 故运算“”是可交换的，即是可交换半群。 推论13.2.1 循环含幺半群都是可交换含幺半群。,2020/9/22,例13.2.8,判断含幺半群是否是循环含幺半群？若是，请求出其所有的生成元。 分析 6 = 0, 1, 2, 3, 4, 5，共有6个元素

10、，则可以判别每一个元素是否是生成元。 解 由于6 = 0, 1, 2, 3, 4, 5，0是幺元，则0肯定不是生成元，对其他元，有： 、1 = 0, 1 = 1, 1 = 2, 1 = 3, 14 = 4, 15 = 5， 所以“1”是的生成元；,2020/9/22,例13.2.8（续）,、2 = 0, 2 = 2, 2 = 0, 2 = 2,， 所以“2”不是的生成元； 、3 = 0, 3 = 3, 3 = 0, 3 = 3,， 所以“3”不是的生成元； 、4 = 0, 4 = 4, 4 = 2, 4 = 0,， 所以“4”不是的生成元； 、5 = 0, 5 = 5, 5 = 4, 5 =

11、3, 54 = 2, 55 = 1， 所以“5”是的生成元。,2020/9/22,例13.2.8（续）,因此，含幺半群有两个生成元“1”、“5”，则是循环含幺半群。 另解 不妨设a6是生成元，则 x6，mN，有x = am = ma (mod 6)， 特别地，当x = 1时，有1 = ma (mod 6)，即 kZ，使得ma = 6k + 1，即 ma + (k)6 = 1。 因此，(a, 6) = 1，即a与6的最大共因子为1。,2020/9/22,例13.2.8（续）,反之，对 a6，如果(a, 6) = 1，则 kZ，使得1 = ma + 6k， 因此，对x6，有 x = (xm)a +

12、 6(xk)，xm，xkZ， 根据“+6”的定义，则 x = axm，xmZ， 因此，a是生成元。,2020/9/22,例13.2.8（续）,综上所述，a6是生成元的充分必要条件是 (a, 6) = 1。 考虑集合6中，可得“1”、“5”是的生成元，则是循环含幺半群。,计算生成元方法： 首先假设生成元存在，然后根据定义得到方程，通过解这个方程来计算生成元。,2020/9/22,推广,（1）是循环含幺半群； （2）对an, 若(a, n) = 1，则a是的生成元； （3）当n是素数时，n中除幺元“0”以外，其他一切元素都是生成元。,2020/9/22,定理与推论,定理13.2.2 在每个有限循环

13、半群中，至少有一个幂等元存在。 推论13.2.2 设为一个有限半群，则中至少存在一个幂等元。,2020/9/22,13.3 群及其性质,定义13.3.1 设为二元代数系统，满足如下性质： （1）“”在G中满足结合律，即a, b, cG，有 (ab) c = a (bc)； （2）G中存在关于“”的幺元e，即eG，使得 aG，ea = ae = a； （3）G中每个元素a都有逆元a1，即aG，都 a1G，aa1 = a1a = e。 则称二元代数系统为群。,概括：群是满足结合律、有幺元，每个元有逆元的二元代数系统为群,2020/9/22,定义13.3.2,在群中， （1）若运算“”满足交换律，即

14、a, bG，都有 ab = ba， 则称为可换群或阿贝尔(Abel)群； （2）集合G的基数称为群G的阶(Order)，记为|G|。若群的阶有限，则称之为有限群，否则称为无限群。,2020/9/22,例13.3.1,证明是群，其中n是正整数。 分析 需要证明4点：封闭性；结合律；幺元存在；逆元存在。 证明 （1）封闭性： x, yn，令 k = x + y (mod n)，则 0kn 1，即kn， 所以封闭性成立。,2020/9/22,例13.3.1（续）,（2）结合律：x, y, zn，有 (x +n y) +n z = x + y + z (mod n) = x +n (y +n z),

15、所以结合律成立。 （3）幺元：xn，显然有 0 +n x = x +n 0， 因此，0是幺元。,2020/9/22,例13.3.1（续）,（4）逆元存在：xn，如果x = 0，显然01 = 0，如果x0，则有 n xn， 显然 x +n (nx) = (nx) +n x = 0， 所以 x1 = (nx)， 因此，xn，x有逆元。 综上，是群。,2020/9/22,例13.3.2,设X是任意集合， S = f：XX | f是双射函数， 运算“”是函数的复合运算，证明是群。 证明 （1）封闭性：f, gS, f, g是双射，则fg也是双射， 即fgS。故封闭性成立。 （2）结合律：由于函数的复合

16、运算“”满足结合律， 因此，在集合S也满足结合律。,2020/9/22,例13.3.2（续）,（3）幺元存在：恒等映射IXG，且fS，有 IX f = f IX = f， 因此，恒等映射IX是幺元。 （4）逆元存在：fS, f是双射，则f1S，且有 f1 f = f f1 = IX， 因此，f1就是f关于“”的逆元。 由（1）、（2）、（3）和（4）可知，是群。,2020/9/22,说明,说明 被称为变换群，如果X是有限集合，设|X| = n，此时称为n阶置换群。变换群在几何学中有十分广泛的应用。,2020/9/22,定理13.3.1,在群中，有： （1）群G中每个元素都是可消去的，即运算满足

17、消去律； （2）群G中除幺元e外无其他幂等元； （3）阶大于1的群G不可能有零元； （4）a, bG，都有(ab)1 = b1a1； （5）群 的的运算表中任意一行(列)都没有两个相同的元素。,2020/9/22,群中元素的周期,设G，*是一个群，对aG，可定义： a=e，a=a，a=a a, an=an- a=a an-=a a a； a-=a-，a-= (a-), a-n=(a-)n= a- a- a-。 由幂方的定义知： am an=am+n=an+m=an am； (am)n=amn。,2020/9/22,元素的周期（续）,对群中的元a，由幂方可得到如下的一个序列： , an，, a2

18、，a1，a0，a1，a2，, an， 这个序列有周期吗？如果有周期，其最小正周期为多少？ 分析 在上述序列中，如果存在整数p和q，其中pq，使得ap = aq，则由消去律有 aqp = e，,2020/9/22,元素的周期（续）,此时pq就是序列的一个周期，因为对任意的整数m，有 am+(pq) = ame = am， 即，对任意的正整数n，如果an = e，则n是序列的周期。,2020/9/22,元素的周期（续）,反之，如果n是序列的周期，肯定有an = e。 为什么呢？ 因为由周期的定义可知，如果n是周期，则 对任意的整数m，由 am+n = am，即aman = am， 由消去律，可得

19、an = e。,2020/9/22,定义13.3.3,设e是群的幺元，aG， （1）使得an = e成立的最小正整数n称为a的周期或为元素a的阶，记为|a|； （2）若不存在这样的正整数n，使得an = e，则称a的周期无限，即对nZ + ，都有an e。 显然，群中幺元e的周期为1,2020/9/22,定理13.3.3,设a是群中的元素，则： （1）如果a的周期为n，则对任意的整数i，有 ai a1, a2, , an ， 且对任意的p, q1, 2, ., n, p q，有 apaq； （2）如果a的周期无限，则对任意的整数p, q, p q，有 apaq； （3）a和它的逆元a1的周期相

20、同。,2020/9/22,例13.3.3,计算实数加群中元素的周期。 分析 在中幺元为“0”，所以有0 = 0， 而对aR，且a0，及nZ + 有 an = an + a = a + an = a + a + + a = na0 ， 因此，此时仅有“0”有周期“1”，而其余元素的周期无限。 结论 在实数加群中，0的周期为1，而其余实数的周期无限。,2020/9/22,定理13.3.5,有限群中每个元素的周期都有限，且不大于群G的阶。 证明 对aG，构造 a, a, a, , an, 由运算“”的满足封闭性知： a, a, a, , an, G， 因为|G|是有限的，所以a, a, a, , a

21、n, 中必有相同的元素，不妨假设： ax = ay （yx），,2020/9/22,定理13.3.5（续）,在式的左右两端同时作用一个ax，有： axax = ay ax = e， 即有： ayx = e （yx0）， 由周期定义可知：元素a的周期一定小于等于(yx)，所以a的周期有限。 如果(yx)大于群G的阶，类似可找到小于G的阶的n，使得an = e,2020/9/22,13.3.3 子群,定义13.3.4 设是群，如果 （1）S是G的非空子集； （2）S在运算“”下也是群，即是群。 则称是的子群。 对任意的群, 和是群G的子群。由于任何群都有这两个子群，故称之为平凡子群，将的非平凡子群

22、称为真子群。,2020/9/22,例13.3.5,计算群的所有子群。 分析 6共有26 1个非空子集，并判别哪些是子群。 解 集合6 = 0, 1, 2, 3, 4, 5的所有的非空子集： 一元子集：0，1，2，3，4，5； 二元子集：0, 1，0, 2，0, 3，0, 4， 三元子集： 四元子集：,2020/9/22,例13.3.5（续）,五元子集：0, 1, 2, 3, 4, 5。 此时仅有四个子集： 0，0, 3，0, 2, 4，0, 1, 2, 3, 4, 5， 关于运算“ +6”满足： （1）封闭性：运算“+6”关于集合0，0, 3，0, 2, 4，0, 1, 2, 3, 4, 5是

23、封闭的； （2）结合律：显然成立；,2020/9/22,例13.3.5（续）,（3）逆元存在： 对集合0，有：01 = 0； 对集合0, 3，有：01 = 0，31 = 3； 对集合0, 2, 4，有： 01 = 0，21 = 4，41 = 2； 对集合0, 1, 2, 3, 4, 5，有： 01 = 0，21 = 4，31 = 3，41 = 2，51 = 1；,2020/9/22,例13.3.5（续）,（4）幺元存在： 对集合0，0, 3，0, 2, 4，0, 1, 2, 3, 4, 5，都有幺元“0”存在； 由（1）、（2）、（3）、（4）知： ，是的子群,2020/9/22,引理13.3

24、.1,设是一个群，是的子群，则: （1）子群的幺元eS也是的幺元eG； （2）对aS，a在S中的逆元aS1就是a在G中的逆元aG1。 证明 （1）eS是的幺元，则 eS2 = eS， 又S G，则eSG，由上式可知eS也是群的一个幂等元。所以有： eS = eG。,2020/9/22,引理13.3.1（续）,（2）对aS，a在S中的逆元为aS1S，则有 a aS1 = aS1 a = eS = eG， 由于S G，所以a，aS1G，有 aS1 = aG1。,引理13.3.1说明，如果S是G的子群，则S的幺元就是G的幺元，S中任意元a在S中的逆元也是a在G中的逆元。,2020/9/22,定理13

25、.3.5,如何判别一个子集是子群？ 定理13.3.5 设S是群的非空子集，S是群G的子群的充分必要条件是： （1）对a, bS，都有abS； （2）对aS，都有a1S。 证明 充分性：要证明是群，需证明运算“”对S封闭，结合律成立，S有幺元和S中的任意元有逆元。,2020/9/22,定理13.3.5（续）,封闭性：由(1)知道运算“” 对S封闭； 结合律：“”在G中满足结合律，S是G的子集，所以“”也在S中满足结合律。 有幺元：S是非空的子集，所以存在元aS，由条件(2)可得 a1S，再由条件(1)知道 aa1S，即G的幺元 e = aa1S。 对任意的bS，eb = be，所以e也是S的幺元

26、。,2020/9/22,定理13.3.5（续）,有逆元：由条件(2)，即对任意aS，都有a1S，则aa1 = a1a = e，又因为已经证明e是S的幺元，所以，在中a1也是a的逆元。 综上，是群，进而是的子群。,2020/9/22,定理13.3.5（续）,必要性：即证明当是的子群时，条件(1)和条件(2)成立。 如果是的子群，显然运算“” 对S封闭，即条件(1) 成立。 根据引理10.1可知，S中a的逆元也是a在G中的逆元，因此有 对aS，都有a1S， 故条件(2)也成立。,2020/9/22,定理13.3.6,设S是群的非空子集，S是子群的充分必要条件是： 对a，bS，都有ab1S。 分析

27、根据定理13.3.5证明 证明 必要性：如果S是G的子群，则对a，bS，由定理13.3.5可知， b1S，进而 ab1S， 所以必要性成立。,2020/9/22,定理13.3.6（续）,充分性：即如果对a，bS，都有ab1S，来证S是G的子群。 S非空，所以存在cS，则由已知有cc1S，即 幺元e = cc1S， 则对aS, ，由已知及eS，有 ea1S，即a1S； 又对a, bS，由bS，则b1S，则 ab a (b1)1S， 由定理13.3.5可知，是的子群。,2020/9/22,例13.3.6,设是一个群，对任意的aG，令 S = an | nZ，Z是整数， 证明是子群。 分析 使用定理

28、13.3.6来证明。 证明 显然S非空。对x, yS，则存在n, mZ， x = an，y = am， 则 xy1 = an (am)1 = anm， 且nmZ，所以 xy1 = anmS， 故由定理13.3.6可得，是的子群。,2020/9/22,推论与定理,推论13.3.1 对群中的任意元a的整数方幂组成的子集是子群，即S = an | nZ，Z是整数是的子群。 如果S是群的有限非空子集，则S还有更弱的判断定理： 定理13.3.7 设S是群的有限非空子集，则S是子群的充分必要条件是 a, bS，有abS。,2020/9/22,定理13.3.7（续）,证明：必要性：显然。 充分性：根据定理1

29、3.3.5，只需证明对aS，有a1S。 对aS，则由已知有 a2 = aaS, a3 = a2aS, ，an = an1aS, ， 令H = an | nN+，则H是S的子集，又S有限，得 p, qN+, p q，ap = aq，则有 a pq = e，且pq 0，,2020/9/22,定理13.3.7（续）,则a的周期有限，设a的周期为n，则 Q = an | nZ，Z是整数 = a1, a2, , an， 由推论13.3.1可知，Q是G的子群，又aQ，则 a1Q， 另一方面，由于a的周期为n，则有 Q = a1, a2, , an = H，则 a1H， 又H是S的子集，则 a1S，,202

30、0/9/22,定理13.3.7（续）,因此，aS，有a1S。又已知a, bS，有abS， 根据定理13.3.5，可得是的子群，故得证。 推论13.3.2 设S是有限群的非空子集，则S是子群的充分必要条件是： a, bS，有abS。,2020/9/22,子群判别方法总结,根据子群的定义，要证明以下5点： 、S非空子集； 、运算对S的封闭性； 、运算在S上结合律成立； 、S上存在幺元； 、S中的每个元都存在逆元。 判别定理13.3.5将5点减少为3点： 、S非空子集； 、运算对S的封闭性； 、S中的每个元的逆元都在S中。,2020/9/22,子群判别方法总结（续）,判别定理13.3.6将后两点融合

31、，并将以上3点进一步减少为2点： 、S非空子集； 、对a，bS，有ab1S。 如果S是有限子集，根据定理13.3.7，则此时只需证明2点： 、S非空子集； 、运算对S的封闭性。 在具体应用中，一般都使用判别定理，特别是定理13.3.5和13.3.6来证明一个非空子集是子群。,2020/9/22,例13.3.6,设是一个交换群，令 S= a| aG且a = a1， 证明是的一个子群。 分析 用定理13.3.6证明，即只需证明两点：、S非空子集；、对a, bS，有ab1S。 对幺元e，有e = e1，因此， eS，所以S非空。 另一方面，要证明ab1S，即是证明 (ab1) = (ab1)1，,2

32、020/9/22,例13.3.6（续）,又(ab1)1 = ba1，因此，只需证明 ab1 = ba1， 又a, bS，可得 a = a1， b = b1。 则只需证明ab = ba， 由于是交换群，故 ab = ba成立。 证明 略。,2020/9/22,例13.3.8,设是整数加群，令： S = 5k | kZ， 证明是的子群。 分析 用定理13.3.6来证明，即只需证明两点： 、S非空子集；、对a，bS，有a + b1S，即证明a + b1 = a bS。 证明 （1）显然S非空；,2020/9/22,例13.3.8（续）,（2）对a, bS，存在k1, k2Z，有 a = 5k1, b

33、 = 5k2，则 a + b1 = 5k1 5k2 5(k1 k2)H (k1 k2Z)， 由（1）、（2）知：是的子群。,2020/9/22,例13.3.9,设是一个群，H1，H2是G的两个子群，证明H = H1H2是G的子群。 分析 根据定理13.3.5，需要证明3点： 、H非空子集；、运算对H的封闭性； 、H中的每个元的逆元都在H中。 证明 （1）非空性：由于H1，H2是G的两个子群，所以有 eH1，eH2，即有eH1H2，故H非空。,2020/9/22,例13.3.9（续）,（2）封闭性：对a, bH，有a, bH1H2，即 a, bH1, a, bH2， 由H1, H2是子群，有 a

34、*bH1, a*bH2，即有a*bH1H2。 （3）逆元存在：对aH，有 aH1H2，即aH1，aH2。由H1，H2是子群，有 a-1H1, a-1H2，即有a-1H1H2。 由（1）、（2）、（3）知：可作成的子群。,2020/9/22,推广,设G，*是一个群，H1，H2，Hn是G的n个子群，则有H= H1H2Hn是G的子群。,2020/9/22,13.3.6群的应用,例13.3.9 Zn = 0, 2, , n 1是整数Z上以n为模的同余等价关系的商集，i, j Zn, i + j = i + j，证明是群。 证明 （1）封闭性：i, j Zn，设i + j = kn + r，其中0 r

35、n 1，有 i + j = i + j = r Zn, 故封闭性成立。,2020/9/22,例13.3.9（续）,（2）结合律：i, j , kZn，有 (i + j) + k = i + j + k = i + (j + k)， 故结合律成立。 （3）幺元：0Zn, iZn，有 0 + i = i + 0 = i, 故0是幺元。,2020/9/22,例13.3.9（续）,（4）逆元：iZn，设i = kn + r，其中0 r n 1，有 i + n r = n r + i = n r + i = n r + kn + r = kn = 0, 因此，n r是i的逆元。 由（1）、（2）、（3）

36、、（4）可知，是群。,2020/9/22,例13.3.10,在书店购买图书时，收银员将光学扫描仪对准书封底上一系列黑白条，就可以在结帐屏幕立即显示应付款。书封底上一系列黑白条代表的是国际标准书号(ISBN)。计算机通过ISBN号库存书信息，并用来记帐。但由于噪声或人为错误，ISBN很容易出错，如输错一位数字或顺序颠倒，计算机如何探测这类错误？如一本书正确的ISBN是7505387081，但是由于光学扫描仪受噪声影响，得到7505387051，计算机怎么识别这是一个错误的ISBN号？,2020/9/22,例13.3.10（续）,分析 一本书在封底通常有国际标准书号(ISBN)，它是10个数字组成

37、的字符串，前九位标识这本书，最后一位是校验位。例如， UNIX初级教程的ISBN号是7505387081， 第一位是7，表示书出版国家(7表示中国)。 第二组数字5053表示出版社(5053表示电子工业出版社)， 第三组数字8708表示出版社对书指定的编号， 最后一位1表示校验位。,2020/9/22,例13.3.10（续）,形式上，ISBN号由10位数字组成： x1x2x10， 其中对i = 1，2，, 9，xi是09的数字， x10是校验位，它有11种可能值：0，2，10，如果校验位等于10，则用罗马数字X表示，因此，x100，2，9，X。 ISBN主要通过校验位来探测ISBN号的错误。如

38、前所述，ISBN由x1x2x10共10位数字确定，而前九位分别代表国家、出版社、出版社对书的编号，这九位数字是事先确定，,2020/9/22,例13.3.10（续）,而校验位通过下式的同余等式确定： 1x1 + 2x2 + + 9x9 = x10 (mod 11)， 在本例中，如果ISBN的前九位是750538708，则校验位x10满足下式： 17 + 25 + 30 + 45 + 53 + 68 + 77 + 80 + 98 = x10 (mod 11)，即 221 = x10 (mod 11)， 则 1 = x10 (mod 11)，,2020/9/22,例13.3.10（续）,由0 x1

39、0 10，得x10 = 1。因此7505387081是正确的ISBN号。 如果前九位是750538705，则校验位x10满足下式： 17 + 25 + 30 + 45 + 53 + 68 + 77 + 80 + 95 = x10 (mod 11)，即 194 = x10 (mod 11)， 则 7 = x10 (mod 11)，,2020/9/22,例13.3.10（续）,由0 x10 10，得x10 = 7。 因此7505387051是错误的ISBN号。 解 计算机使用同余关系，通过校验位来发现7505387051是错误的ISBN号。,2020/9/22,13.4 特殊群,特殊群主要有三类：

40、 交换群、循环群、变换群（置换群）,2020/9/22,13.4.1 交换群（阿贝尔群）,若群中的运算“”满足交换律，则称是一个交换群（阿贝尔（Abel）群）。 由于加法运算“+”满足交换律，因此群，都是交换群。,2020/9/22,定理13.4.1,设是一个群，则是交换群的充分必要条件是： 对a, bG，有(a*b)2 = a2*b2。 证明 必要性：对a, bG，由于 “*” 可交换，所以有 (a*b)2 = (a*b)*(a*b) = a*(b*a)*b = a(ab)*b = (a*a)*(b*b) = a2*b2。,2020/9/22,定理13.4.1（续）,充分性：对a, bG，若

41、有(a*b)2 = a2*b2，则 (a*b)2 = (a*b)*(a*b) = (a*a)*(b*b)， 因此， a*(b*a)*b = a*(a*b)*b， 由消去律知： b*a = a*b， 所以，运算“*”满足交换律，即是交换群。,2020/9/22,13.4.2 循环群,定义13.4.2 在群中，若存在元素gG，使得对aG，都有： a = gi（iZ，Z为整数集合）， 则称为循环群，记为G = (或= )，并称g为该循环群的一个生成元。G的所有生成元的集合称为G的生成集。,计算群的生成元是判别一个群是否是循环群的关键。,2020/9/22,定理13.4.2,每个循环群都是阿贝尔群。

42、证明 设gG是循环群的生成元，对n，mG，存在x，yZ，有 n = gx，m = gy， 则 n*m = gx*gy = gx+y = gy+x = gy*gx = m*n， 所以，循环群是阿贝尔群。,2020/9/22,例13.4.1,证明整数加法群是循环群，并求其所有的生成元。 分析 不妨设aZ是生成元，则由生成元的定义，对nZ，存在kZ，使得 n = ak = ka， 特别取n = 1，则有 1 = ak， 又a, k都是整数，所以必然有 a = 1，或a = -1。 以上说明，如果a是生成元，则a必须是1或者-1，因此，还需进一步验证1是否是的生成元。,2020/9/22,例13.4.

43、1（续）,证明 因为对nZ，有 n = 1 + 1 + + 1 = 1n， n = 1 + 1 + + 1 = (1)1 + (1)1 + + (1)1 = (1)1)n = (-1)(-n)， 所以1是生成元，故是循环群，其生成集为-1, 1。,2020/9/22,结论,判别群是否是循环群主要就是计算生成元，而计算生成元有两步： 、假设生成元存在，并根据定义计算它； 、验证计算的结果是否是生成元，如果是，则该群是循环群。,2020/9/22,例13.4.2,证明群(nZ +)是循环群，并求出生成集。 证明 设a是生成元，则对mn，存在kZ，使得 m = ak = ka (mod n)， 特别

44、取m = 1，则有 1 = ka(mod n)， 即存在sZ，使得 ns + ka = 1， 所以有(a, n) = 1，即a与n互质。,2020/9/22,例13.4.2（续）,这说明，如果a是生成元，则有a与n互质。 反之，如果(a, n) = 1，则 s, tZ，有 ns+ta = 1，即 1 = ta(mod n)， 所以有 1 = at (tZ)，,2020/9/22,例13.4.2（续）,则对mn，有 m = 1m = (at)m = atm(tnZ)， 故a是生成元。 因此a是生成元的充要条件是(a, n) = 1。 群的生成集为 M = a | (an)(n, a) = 1)，

45、 显然1M，所以1是的生成元，即对mn， m = 1m， 故是循环群。,2020/9/22,结论,（1）群是一个循环群，其生成集为 M = a| (an)(n, a) = 1)； （2）素数阶的循环群，除幺元以外的一切元素都是群的生成元。,2020/9/22,两类循环群,G = 是循环群，根据生成元g的周期，可得两类循环群： （1）当g的周期无限时，是无限阶循环群，则 =gk | kZ；若ij，则gigj； （2）当g的周期有限时，是有限阶循环群，若g的周期为n，则有 = e, g, g2, g3, gn-1。,2020/9/22,定理13.4.3,设是以g为生成元的循环群，则 （1）若G是无

46、限集，则G与整数加法群同构； （2）若|G| = n，则G与n阶剩余类加群同构。 证明 略。,2020/9/22,结论,（1）无限循环群有且仅有两个生成元； （2）阶为素数的循环群除幺元以外的一切元素都是G的生成元； （3）阶为正整数n的循环群G = ，对y = axG，只要(n, x) = 1，则y一定是G的生成元；,2020/9/22,结论（续）,（4）循环群的子群一定是循环群； （5）若G = 是一个n阶的循环群，则由n的一切因子d都可对应产生一个且仅一个d阶子群，该d阶循环子群的生成元为ax，其中x = n/d； （6）阶为素数p的循环群G = 不含有非平凡的真子群。,2020/9/2

47、2,定理13.4.4,设aG是群中的任意元素，令 S = an | nZ，Z是整数， 证明是的循环子群。 证明 略。 定理13.4.4说明，群中每个元素的整数方幂集合是该群的循环子群。,2020/9/22,例13.4.4,证明群是循环群。 证明 1Zn，对i Zn，有 i = 1 + 1 + + 1 = 1 + 1 + + 1 = 1i， 因此1是生成元，所以是循环群。 说明 是n阶循环群，它与同构。本质上，是的一个简化。,2020/9/22,13.5 陪集与拉格朗日定理,13.5.1 陪集 定义13.5.1 设是群，是的任意子群，对a, bG，如果有a*b-1H，则称a, b为模H同余关系，

48、此时记为ab(modH)。,2020/9/22,定理13.5.1,设是的任一个子群，证明模H同余关系是G上的等价关系。 证明 （1）自反性：对aG，有a-1G，所以 a*a-1 = eH， 即 aa(modH)， 所以模H同余关系是自反关系。,2020/9/22,定理13.5.1（续）,（2）对称性：a，bG，如有ab(modH)，即 a*b-1H， 因H是一个群，所以有 b*a-1 = (b-1)-1*a1 = (a*b1)-1H，即 ba(modH)， 所以模H同余关系是对称关系。,2020/9/22,定理13.5.1（续）,（3）传递性：a, b, cG，如有ab(modH)，bc(mo

49、dH)，则 a*b-1H，b*c-1H， 因H是一个群，所以有 a*c-1 = (a*b-1)*(b*c-1)H，即 ac(modH)， 所以模H同余关系是传递关系。 由（1）、（2）、（3）得证。,2020/9/22,陪集和拉氏定理,考虑其等价类：对aG，有： aR=x|(一切xG)(xa(modH) =x|(一切xG)(h=x*a-1H) =h*a|(一切hH) 记Ha=h*a|(一切hH)=aR， 称Ha为H在G，*中的一个右陪集。 同理，可定义G，*的左陪集。,2020/9/22,定义13.5.2,设是群的子群，a是G中任意元素，称 （1）aH = a*hhH为子群H在群G中的一个左陪

50、集； （2） Ha = h*ahH为子群H在群G中的一个右陪集。 a称为左陪集aH（或右陪集Ha）的代表元。,2020/9/22,例13.5.1,计算群的子群 的一切左、右陪集。 解 令H = 0, 2, 4，则所有的右陪集有： H0 = 0, 2, 40 = 0, 2, 4， H1 = 0, 2, 41 = 1, 3, 5， H2 = 0, 2, 42 = 2, 4, 0， H3 = 0, 2, 43 = 3, 5, 1， H4 = 0, 2, 44 = 4, 0, 2， H5 = 0, 2, 45 = 5, 1, 3，,2020/9/22,例13.5.1（续）,即 H0 = H2 = H4

51、, H1 = H3= H5, H0H1 = 6； 同理，所有的左陪集有 0H = 00, 2, 4 = 0, 2, 4， 1H = 10, 2, 4 = 1, 3, 5， 2H = 20, 2, 4 = 2, 4, 0， 3H = 30, 2, 4 = 3, 5, 1， 4H = 40, 2, 4 = 4, 0, 2， 5H = 50, 2, 4 = 5, 1, 3， 有:0H = 2H = 4H，1H = 3H= 5H，0H1H = 6。,2020/9/22,例13.5.2,设G = ，H = kmkZ，则H是G的子群，计算H的左、右陪集。 解 根据定义，所有的左、右陪集为： 0H = H0

52、 = H = kmkZ， 1H = H1 = km+1kZ， (m-1)H = H(m-1) = km+m-1kZ。,2020/9/22,性质13.5.1,设是群的子群，e是幺元，a，bG，则 （1）eH = H = He； （2）Ha = H aH（aH = H aH）； （3）aHb Ha = Hb a*b1H（abH aH = bH a1*bH）。,2020/9/22,求陪集的方法,设H是有限群G的一个子群，求H的左、右陪集： (1) 首先H本身是G的一个左、右陪集； (2) 任取aG，但a H，求aH，Ha，此时有： HaH，HHa；又得一个左、右陪集； (3)任取bG，但b HHa，求bH，Hb，此时 HaHbH，HHaHb； 又得一个左、右陪集；,2020/9/22,求陪集的方法（续）,(4)反复上述过程，有： G HaHbH HHaHb。,2020/9/22,性质13.5.2,设是群的子群，则 （1）对aG，有|Ha| = |H| = |aH|； （2）对bG，有|Hb| = |H| = |bH|； （3）对a，bG，有|aH| = |bH| = |Ha| = |Hb|。 证明 略。,2020/9/22,13.5.2 拉格朗日定理,有限群的阶n一定被它的任意子群的阶m所等分，即k