第三章 循环群 群的结构 信息安全数学

1、电子科技大学电子科技大学 计算机科学与工程学院计算机科学与工程学院UESTC Press 第三章 循环群、群的结构第三章第三章 循环群、群的结构循环群、群的结构电子科技大学电子科技大学 计算机科学与工程学院计算机科学与工程学院UESTC Press 第三章 循环群、群的结构第三章第三章 循环群、群的结构循环群、群的结构3.1 循环群（循环群（重要重要）3.2 剩余类群（剩余类群（掌握掌握）3.3 子群的陪集（子群的陪集（掌握掌握）3.4 正规子群、商群（正规子群、商群（重要重要）电子科技大学电子科技大学 计算机科学与工程学院计算机科学与工程学院UESTC Press 第三章 循环群、群的结构3

2、.1 循环群循环群定义定义3.1.1如果一个群G里的元素都是某一个元素g的幂，则G称为循环群，g称为G的一个生成元由g生成的循环群记为(g)无限循环群可表示为：，g2，g1，g0，g1，g2，其中g0 = e有限n阶循环群可表示为： g0，g1，g2，gn1，其中g0 = e 电子科技大学电子科技大学 计算机科学与工程学院计算机科学与工程学院UESTC Press 第三章 循环群、群的结构3.1 循环群循环群例例3.1.1整数加法群Z是一个循环群1是生成元，每一个元素都是1的“幂”这里再次说明我们讨论的群里“乘法”是抽象的，只代表一种代数运算在整数加群中，“乘法”就是普通加法，那么“幂”就是一

3、个元素的连加，例如1mm = ，1mm = 而且规定0 = 10，即0为0个1相加111m ( 1)( 1)( 1)m 电子科技大学电子科技大学 计算机科学与工程学院计算机科学与工程学院UESTC Press 第三章 循环群、群的结构循环群简单性质循环群简单性质由n阶循环群中gn = e，我们可以得到：设i，j是任意整数，1）如果i j (mod n)，则gi = gj2）gi的逆元gi = gni3）是交换群4）gn=e电子科技大学电子科技大学 计算机科学与工程学院计算机科学与工程学院UESTC Press 第三章 循环群、群的结构循环群简单性质循环群简单性质对于循环群G中两个任意元gigj

4、 = gi+j = gj+i = gjgi，所以循环群一定满足交换律，是交换群（Abel群）在n阶循环群中，有gn = e因为如果gn e，假设gn = gi (0in1)，则由消去律得gni = e (0nin1)，这与n阶循环群的定义矛盾循环群是交换群电子科技大学电子科技大学 计算机科学与工程学院计算机科学与工程学院UESTC Press 第三章 循环群、群的结构元素的阶及其性质元素的阶及其性质 1）a的所有幂两两不相等，于是以a为生成元的循环群，a2，a1，a0 = e，a1，a2，是无限循环群2）存在整数ij，使ai = aj，则aij = e这表明存在正整数k = ij使ak = e

5、我们称使上式成立的最小正整数n称为元素a的阶在第1种情况下，这样的正整数不存在，称a是无限阶元素无限阶元素电子科技大学电子科技大学 计算机科学与工程学院计算机科学与工程学院UESTC Press 第三章 循环群、群的结构元素的阶及其性质元素的阶及其性质a是n阶元素，则序列a0 （= e），a1，a2，an1两两不相同，而且a的一切幂都包含在这个序列中。 证明：证明：（反证法）如果ai = aj，0 j i n1，则aij = e，而0 ij n1，这与a是n阶元素矛盾对于任意整数m，am都包含在上面的序列中m可表示为：m = qn + r，0rn，于是am = aqn + r = (aq)na

6、r = ar，因为ar在上面的序列中，则am也在上面的序列中 电子科技大学电子科技大学 计算机科学与工程学院计算机科学与工程学院UESTC Press 第三章 循环群、群的结构元素的阶及其性质元素的阶及其性质定理定理3.1.1 一个群G的任意元素a都能生成一个循环群，它是G的子群如果a是无限阶元素，则a生成无限循环群；如果a是n阶元素，则a生成n阶循环群证明证明设a的幂集合为S1）a是无限阶元素情形对于任意ai，ajS (i，j = 0，1，2，)，有ai(aj)1 = aijS，由定理2.2.2，S是G的子群2）a是n阶元素情形对于任意ai，ajS (i，j = 0，1，2，)，有aiaj

7、= ai+jS，由定理2.2.3，S是G的子群显然S是a生成的循环群定理证毕显然无限循环群的元素都是无限阶元素显然无限循环群的元素都是无限阶元素有限循环群生成元的阶就是群的阶有限循环群生成元的阶就是群的阶 电子科技大学电子科技大学 计算机科学与工程学院计算机科学与工程学院UESTC Press 第三章 循环群、群的结构元素的阶及其性质元素的阶及其性质定理定理3.1.2对于n阶元素a有1）ai = e，当且仅当ni2）ak的阶为 证明证明n阶元素a生成n阶循环群：a0 = e，a1，a2，an11）由于ni，则i 0(mod n)，于是ai = a0= e反之，由i = qn + r，0rn，得

8、ai = aqn+r= (an)qar = ear= ar = e，而n是使ak = e的最小正整数，所以r = 0，故ni(,)nkn电子科技大学电子科技大学 计算机科学与工程学院计算机科学与工程学院UESTC Press 第三章 循环群、群的结构元素的阶及其性质元素的阶及其性质2）设l = 由于(k，n)k，则于是由1）有(ak)l = akl = e而如果(ak)i = aki = e，则nki，因为所以 故是使(ak)i = e，成立的最小正整数证毕(,)nkn()( , )nn kklk n( , ) ()nkik nkn，(,)1() ()nkknkn，(,)nikn( , )nk

9、 n电子科技大学电子科技大学 计算机科学与工程学院计算机科学与工程学院UESTC Press 第三章 循环群、群的结构元素的阶及其性质元素的阶及其性质由定理定理3.1.2我们可以直接得出推论推论由元素g生成的n阶循环群G中任意元素gk(0kn1)的阶为，当k，n互素时，gk的阶为n，也是G的生成元例例3.1.28阶循环群各个元素的阶分别为：g0：1，g：8，g2：4，g3：8，g4：2，g5：8，g6：4，g7：8其中共有4个生成元g，g3，g5，g7整数集合0，1，2，n1中与n互素的数有(n)个（(n)欧拉函数，以后我们还要深入讨论），因此n阶循环群共有(n)个n阶元素或(n)个生成元 电

10、子科技大学电子科技大学 计算机科学与工程学院计算机科学与工程学院UESTC Press 第三章 循环群、群的结构循环群与其子群循环群与其子群定理定理3.1.31）循环群的子群是循环群，它或者仅由单位元构成，或者由子群中具有最小正指数的元素生成，即生成元为具有最小正指数的元素；2）无限循环群的子群除e外都是无限循环群；3）有限n阶循环群的子群的阶是n的正因子，且对n的每一个正因子q，有且仅有一个q阶子群电子科技大学电子科技大学 计算机科学与工程学院计算机科学与工程学院UESTC Press 第三章 循环群、群的结构循环群与其子群循环群与其子群证明证明1） 设H是循环群(g)的一个子群 假设He，

11、H自然是循环群假设He，则有i0使giH，又因为gi=(gi)1H，所以可以假定i0，说明有正指数存在设s是H中的最小正指数，即s是使gsH的最小正整数，我们现在证明H = (gs)对于任意gmH，有m = qs+t，0ts，由于gqs= (gs)qH（子群H的封闭性，q个gs连乘也属于H），所以gt = gm(gqs)1H，（gqs存在逆元，且由于封闭性，gm，(gqs)1乘积属于H）由于s是使gsH的最小正整数，因此得t = 0，gm(gs)qH的任意元素都是gs的幂，则H = (gs) 电子科技大学电子科技大学 计算机科学与工程学院计算机科学与工程学院UESTC Press 第三章 循环

12、群、群的结构循环群与其子群循环群与其子群证明证明2）当(g)是无限循环群时，如果n m，则gn gm，于是gms (m=0，1，2，)两两不同，H是无限循环群证明证明3）假设(g)是n阶循环群，由于n = qs+t，0ts，则e = gn = gqs+t，于是gt = (gqs)1H，s的最小性使得t = 0，所以n = qs，H可表示为H = e，gs，g(q1)s 当s = n时H = e 电子科技大学电子科技大学 计算机科学与工程学院计算机科学与工程学院UESTC Press 第三章 循环群、群的结构循环群与其子群循环群与其子群 上页不仅证明了H的阶q是n的正因子，而且给出n的正因子q阶

13、子群当q跑遍n的所有正因子时，s也跑遍n的正因子，所以对于n的每一个正因子q，都有而且仅有一个q阶循环子群电子科技大学电子科技大学 计算机科学与工程学院计算机科学与工程学院UESTC Press 第三章 循环群、群的结构循环群与其子群循环群与其子群例例3.1.38阶循环群G的真子群8的所有正因子为1，2，4，8相应的子群分别为e， e，g4， e，g2，g4，g6，G其中e和G是群G的平凡子群电子科技大学电子科技大学 计算机科学与工程学院计算机科学与工程学院UESTC Press 第三章 循环群、群的结构3.2 剩余类群剩余类群剩余类的概念：剩余类的概念：根据同余的概念，我们可以将全体整数Z进

14、行分类：设m是正整数，把模m同余的整数归为一类，即可表示为a = qm+r， 0 r m，q = 0，1，2，的整数为一类，称为剩余类剩余类，剩余类中的每个数都称为该类的剩余剩余或代表代表，r称为该类的最小非负剩余最小非负剩余电子科技大学电子科技大学 计算机科学与工程学院计算机科学与工程学院UESTC Press 第三章 循环群、群的结构剩余类群剩余类群例例3.3.1m = 8，r = 5的剩余类为5，18+5，28+5，38+5，这样我们将全体整数按模m分成m个剩余类：这m个剩余类可分别表示为： = 0，m，2m，3m，； = 1，1m，12m，13m，； = 2，2m，22m，23m，；

15、= (m1)，(m1)m，(m1)2m，(m1)3m，这m个剩余类称为模模m剩余类剩余类记为Z Zm m0,1,2,(1)m012(1)m电子科技大学电子科技大学 计算机科学与工程学院计算机科学与工程学院UESTC Press 第三章 循环群、群的结构剩余类群剩余类群设 和 是两个模m的剩余类，定义剩余类的加法如下：如Z8的两个剩余类 和ijijij24246电子科技大学电子科技大学 计算机科学与工程学院计算机科学与工程学院UESTC Press 第三章 循环群、群的结构剩余类群剩余类群定理定理3.2.1模m的全体剩余类集合对于剩余类加法构成m阶循环群证明证明 封闭性和结合律显然满足 是单位元

16、， 的逆元是故剩余类集合是一个群该群是一个循环群，生成元是，注意对于加法，元素的“幂”就是元素的连加0iimi 电子科技大学电子科技大学 计算机科学与工程学院计算机科学与工程学院UESTC Press 第三章 循环群、群的结构剩余类群剩余类群定理定理3.2.2任意无限循环群与整数加群Z同构，任意有限n阶循环群与n阶剩余类加群同构证明证明设(g)任意循环群如果(g)是无限循环群，做整数加群Z到(g)的映射如下：对于任意kZ，有 f(k) = gk，这是一个一一映射，而且对于k，hZ，f(k)f(h) = gkgh = gk+h = f(k+h)故f是Z到(g)的同构映射，(g)与Z同构电子科技大

17、学电子科技大学 计算机科学与工程学院计算机科学与工程学院UESTC Press 第三章 循环群、群的结构剩余类群剩余类群（证明续证明续）如果(g)是n阶循环群，做模m剩余类加群Zm到(g)的映射：对于任意 Zm，f( ) = gk，这显然是一一映射，而且对于， Zm ，f( )f( ) = gk gh = gk+h = f( )故f是Zm到(g)的同构映射，(g)与Zm同构定理定理3.2.2的意义在于通过了解整数加群和剩余类加群，就了解了一切无限循环群和有限循环群的构造 kkhkhhk电子科技大学电子科技大学 计算机科学与工程学院计算机科学与工程学院UESTC Press 第三章 循环群、群的

18、结构3.3 子群的陪集子群的陪集引理引理设G是一个群1）对于任意aG，集合aG = ah | hG= G2）GG = ah | hG，aG= G电子科技大学电子科技大学 计算机科学与工程学院计算机科学与工程学院UESTC Press 第三章 循环群、群的结构子群的陪集子群的陪集证明证明1）a，h都是G的元素，由G的封闭性，我们有ahG则对于任意baG，总有bG，于是aG G对于任意bG，我们有b = eb = (aa1)b = a(a1b)，由于a1bG，所以b = a(a1b)aG，于是G aG故G = aG2）a GGGaGGG电子科技大学电子科技大学 计算机科学与工程学院计算机科学与工程

19、学院UESTC Press 第三章 循环群、群的结构子群的陪集子群的陪集定义定义3.3.1设H是群G的一个子群对于任意aG，集合ah | hH 称为H的一个左陪集左陪集，记为aH同样我们定义右陪集右陪集Ha = ha | hH 对于交换群（阿贝尔群），左陪集和右陪集是一致的，可以称为陪集陪集电子科技大学电子科技大学 计算机科学与工程学院计算机科学与工程学院UESTC Press 第三章 循环群、群的结构（1）（2） 这说明陪集中的任何元素均可以作为代表元。 （3）两个陪集相等的条件（4）对任何a，bG有aH=bH或 因而H的所有左陪集的集合aHa G构成了G的划分。陪集的性质陪集的性质aHHa

20、H.baHaHbH11()aHbHa bH HaHbbaHaHbH 所有性质对右陪集也成立电子科技大学电子科技大学 计算机科学与工程学院计算机科学与工程学院UESTC Press 第三章 循环群、群的结构陪集的性质陪集的性质证明：（1） 若aH，aH=ahh H，显然有aH=H;反之，若aH=H，即任意hH，有ah H,则有ah=e，a-1 H，故a H（2）若b aH，则b=ah0 h0 H ）， bH=ah0H=a（h0H）=aH，反之，bH=aH，存在bh1=ah2，有b=ah2h1-1 aH ，即b aH （其中h0，h 1，h2H ）（3）若aH=bH，则存在h 1，h2H ,ah1

21、=bh2，有a-1b=h1h2-1 H ，反之，若a-1b H ，有b aH ,由（2）知，bH=aH电子科技大学电子科技大学 计算机科学与工程学院计算机科学与工程学院UESTC Press 第三章 循环群、群的结构陪集的性质陪集的性质（4）任何a，b G，有，aH=bH或 这是因为如果 ，则存在 x aHbH ，于是 x=ah1=bh2 ，得a-1b=h1h2-1 H，由性质（3）知，aH=bH，又因为任何一个元素a均可以作陪集aH，因而 ，所以aHa G是G的一个划分。aHbH aHbH a GG=aH电子科技大学电子科技大学 计算机科学与工程学院计算机科学与工程学院UESTC Press

22、 第三章 循环群、群的结构陪集的性质陪集的性质陪集的性质（4）整理成定理3.3.1定理定理3.3.1设H是群G的一个子群H的任意两个左（右）陪集或者相等或者无公共元素群G可以表示成若干互不相交的左（右）陪集的并集电子科技大学电子科技大学 计算机科学与工程学院计算机科学与工程学院UESTC Press 第三章 循环群、群的结构陪集的性质陪集的性质例例3.3.2设m是一个正整数，M表示所有m的倍数组成的集合，即M = mt | t = 0，1，2，3， = 0，m，2m，3m，M的另一种表示为M = mt | tZ显然M是整数加群Z的子群设为模m的一个剩余类，即 于是我们有可见 是M的一个陪集由Z

23、可以按模m分成m个剩余类，则Z可以按M分成m个陪集：M，1+M，2+M，(m1)+Mi+mt | tZ i i+Mi i+Mi 电子科技大学电子科技大学 计算机科学与工程学院计算机科学与工程学院UESTC Press 第三章 循环群、群的结构子群的指数及子群的指数及Lagrange定理定理下面我们讨论两个问题：1）陪集元素数目是多少？2）陪集也可以成为子群吗？引理：引理：设G是群，H是G的子群（HG），SL=aHaG， SR=aHaG，则存在SL到SR的双射。证明：作SL到SR的一个对应关系：aH Ha-1（ SL SR ），因为 所以是映射且是单射。又对任意Ha SR，取a-1H SL，则

24、（ a-1H ）=Ha，所以也是满射。即命题得证。111121212a Ha Ha aHHaHa电子科技大学电子科技大学 计算机科学与工程学院计算机科学与工程学院UESTC Press 第三章 循环群、群的结构子群的指数及子群的指数及Lagrange定理定理集合SL和SR是等势的，当他们是有限集合时，左陪集的个数等于右陪集的个数： SL = SR ，称为H在在G中的指数中的指数,记作记作G：H。另外，从引理的证明中，我们不难发现，对于有限子群H，每个左（右）陪集内元素数目都等于H的阶；即 aH = H ，且由于eH，则 ，即 H的其他陪集中不含单位元e，所以它们不可能是群故H的陪集除H外对于G

25、的运算都不是群()eaHaH当电子科技大学电子科技大学 计算机科学与工程学院计算机科学与工程学院UESTC Press 第三章 循环群、群的结构子群的指数及子群的指数及Lagrange定理定理推论推论1 （拉格朗日定理）设G是一个有限群，H是一个子群，则H的阶是G的阶的因子即 G= H G:H 推论推论2设G是一个有限群，G中的每一个元素的阶一定是G的阶的因子设G的阶为n，则对任意aG，有an = e推论1、2证明比较简单，请同学自己尝试证明电子科技大学电子科技大学 计算机科学与工程学院计算机科学与工程学院UESTC Press 第三章 循环群、群的结构子群的指数及子群的指数及Lagrange

26、定理定理推论推论3阶为素数的群一定为循环群证明证明设群G的阶为素数，即|G|是素数当|G| = 1时，群G是只含单位元e的循环群当|G| 1时，取aG且a e，则a生成一个循环子群H，且|H| 1由于|H|是|G|的的因子，而当|G|是素数时，它只有1和|G|两个因子，故|H| = |G|，这表明H = G，G是一个循环群电子科技大学电子科技大学 计算机科学与工程学院计算机科学与工程学院UESTC Press 第三章 循环群、群的结构3.4 正规子群、商群正规子群、商群定义定义3.4.1设H是群G的子群如果H的每一个左陪集也是右陪集，即对于任意aG，总有aH = Ha，则称H为G的正规子群正规

27、子群，或不变子群不变子群显然阿贝尔群的所有子群是正规子群电子科技大学电子科技大学 计算机科学与工程学院计算机科学与工程学院UESTC Press 第三章 循环群、群的结构正规子群正规子群定理定理3.4.1设H是群G的子群则下面4个命题是等价的1）H是群的正规子群；2）对于任意aG，总有aHa1 = H；3）对于任意aG及任意hH，总有aha1H 4）对于任意aG，总有aHa1H电子科技大学电子科技大学 计算机科学与工程学院计算机科学与工程学院UESTC Press 第三章 循环群、群的结构正规子群正规子群证明证明我们通过证明1)2)3)4)1)，从而证明4个命题等价1)2)：如果H是正规子群，

28、则aHa1 = (aH) a1 = (Ha) a1 =H (aa1) = He = H2)3)：显然3)4)：也是显然4)1)：由aHa1H，得aHHa；又由a1HaH（注意对于任意aG，有aHa1H，而a1G，所以a1HaH），得HaaH故Ha = aH定理证毕定理3.4.1表明，子群是正规子群的充分必要条件是2或者3或者4电子科技大学电子科技大学 计算机科学与工程学院计算机科学与工程学院UESTC Press 第三章 循环群、群的结构正规子群正规子群定义定义3.4.2设A，B是群G中的两个子集合，定义子集合子集合A和和B的乘积的乘积为AB = ab | a，bG，即为A中元素和B中元素相乘得到的集合显然子集乘积满足结合律：(AB)C = A(BC)如果A是一个子群，bG，令B = b，则G的左陪集bA可表示为BA电子科技大学电子科技大学 计算机科学与工程学院计算机科学与工程学院UESTC Press 第三章 循环群、群的结构正规子群正规子群定理定理3.4.2设H是群G的一