循環(huán)群群的結(jié)構(gòu)信息安全數(shù)學(xué)課件

1、循環(huán)群群的結(jié)構(gòu)信息安全數(shù)學(xué),1,第三章 循環(huán)群、群的結(jié)構(gòu),循環(huán)群群的結(jié)構(gòu)信息安全數(shù)學(xué),2,第三章 循環(huán)群、群的結(jié)構(gòu),3.1 循環(huán)群（重要） 3.2 剩余類群（掌握） 3.3 子群的陪集（掌握） 3.4 正規(guī)子群、商群（重要,循環(huán)群群的結(jié)構(gòu)信息安全數(shù)學(xué),3,3.1 循環(huán)群,定義3.1.1如果一個(gè)群G里的元素都是某一個(gè)元素g的冪，則G稱為循環(huán)群，g稱為G的一個(gè)生成元由g生成的循環(huán)群記為(g) 無(wú)限循環(huán)群可表示為： ，g2，g1，g0，g1，g2，其中g(shù)0 = e 有限n階循環(huán)群可表示為： g0，g1，g2，gn1，其中g(shù)0 = e,循環(huán)群群的結(jié)構(gòu)信息安全數(shù)學(xué),4,3.1 循環(huán)群,例3.1.1整數(shù)加

2、法群Z是一個(gè)循環(huán)群1是生成元，每一個(gè)元素都是1的“冪”這里再次說(shuō)明我們討論的群里“乘法”是抽象的，只代表一種代數(shù)運(yùn)算在整數(shù)加群中，“乘法”就是普通加法，那么“冪”就是一個(gè)元素的連加，例如 1mm = ， 1mm = 而且規(guī)定 0 = 10， 即0為0個(gè)1相加,循環(huán)群群的結(jié)構(gòu)信息安全數(shù)學(xué),5,循環(huán)群簡(jiǎn)單性質(zhì),由n階循環(huán)群中g(shù)n = e，我們可以得到：設(shè)i，j是任意整數(shù)， 1）如果i j (mod n)，則 gi = gj 2）gi的逆元 gi = gni 3）是交換群 4）gn=e,循環(huán)群群的結(jié)構(gòu)信息安全數(shù)學(xué),6,循環(huán)群群的結(jié)構(gòu)信息安全數(shù)學(xué),7,循環(huán)群群的結(jié)構(gòu)信息安全數(shù)學(xué),8,元素的階及其性質(zhì),

3、a是n階元素，則序列 a0 （= e），a1，a2，an1 兩兩不相同，而且a的一切冪都包含在這個(gè)序列中。 證明：（反證法）如果 ai = aj，0 j i n1， 則aij = e，而0 ij n1，這與a是n階元素矛盾 對(duì)于任意整數(shù)m，am都包含在上面的序列中m可表示為： m = qn + r，0rn， 于是 am = aqn + r = (aq)nar = ar， 因?yàn)閍r在上面的序列中，則am也在上面的序列中,循環(huán)群群的結(jié)構(gòu)信息安全數(shù)學(xué),9,元素的階及其性質(zhì),定理3.1.1 一個(gè)群G的任意元素a都能生成一個(gè)循環(huán)群，它是G的子群如果a是無(wú)限階元素，則a生成無(wú)限循環(huán)群；如果a是n階元素，則

4、a生成n階循環(huán)群 證明設(shè)a的冪集合為S 1）a是無(wú)限階元素情形 對(duì)于任意ai，ajS (i，j = 0，1，2，)，有 ai(aj)1 = aijS， 由定理2.2.2，S是G的子群 2）a是n階元素情形 對(duì)于任意ai，ajS (i，j = 0，1，2，)，有 aiaj = ai+jS， 由定理2.2.3，S是G的子群 顯然S是a生成的循環(huán)群定理證畢,顯然無(wú)限循環(huán)群的元素都是無(wú)限階元素 有限循環(huán)群生成元的階就是群的階,循環(huán)群群的結(jié)構(gòu)信息安全數(shù)學(xué),10,元素的階及其性質(zhì),定理3.1.2對(duì)于n階元素a有 1）ai = e，當(dāng)且僅當(dāng)ni 2）ak的階為 證明n階元素a生成n階循環(huán)群： a0 = e，

5、a1，a2，an1 1）由于ni，則i 0(mod n)， 于是ai = a0= e 反之，由 i = qn + r，0rn， 得ai = aqn+r= (an)qar = ear= ar = e， 而n是使ak = e的最小正整數(shù)，所以r = 0，故ni,循環(huán)群群的結(jié)構(gòu)信息安全數(shù)學(xué),11,元素的階及其性質(zhì),2）設(shè)l = 由于(k，n)k，則 于是由1）有(ak)l = akl = e 而如果(ak)i = aki = e， 則nki， 因?yàn)?所以 故 是使(ak)i = e， 成立的最小正整數(shù)證畢,循環(huán)群群的結(jié)構(gòu)信息安全數(shù)學(xué),12,元素的階及其性質(zhì),由定理3.1.2我們可以直接得出 推論由元

6、素g生成的n階循環(huán)群G中任意元素gk(0kn1)的階為，當(dāng)k，n互素時(shí)，gk的階為n，也是G的生成元 例3.1.28階循環(huán)群各個(gè)元素的階分別為： g0：1，g：8，g2：4，g3：8， g4：2，g5：8，g6：4，g7：8 其中共有4個(gè)生成元g，g3，g5，g7 整數(shù)集合0，1，2，n1中與n互素的數(shù)有(n)個(gè)（(n)歐拉函數(shù)，以后我們還要深入討論），因此n階循環(huán)群共有(n)個(gè)n階元素或(n)個(gè)生成元,循環(huán)群群的結(jié)構(gòu)信息安全數(shù)學(xué),13,循環(huán)群與其子群,定理3.1.31）循環(huán)群的子群是循環(huán)群，它或者僅由單位元構(gòu)成，或者由子群中具有最小正指數(shù)的元素生成，即生成元為具有最小正指數(shù)的元素； 2）無(wú)限

7、循環(huán)群的子群除e外都是無(wú)限循環(huán)群； 3）有限n階循環(huán)群的子群的階是n的正因子，且對(duì)n的每一個(gè)正因子q，有且僅有一個(gè)q階子群,循環(huán)群群的結(jié)構(gòu)信息安全數(shù)學(xué),14,循環(huán)群與其子群,證明1） 設(shè)H是循環(huán)群(g)的一個(gè)子群 假設(shè)He，H自然是循環(huán)群假設(shè)He，則有i0使giH，又因?yàn)間i=(gi)1H，所以可以假定i0，說(shuō)明有正指數(shù)存在 設(shè)s是H中的最小正指數(shù)，即s是使gsH的最小正整數(shù)，我們現(xiàn)在證明H = (gs)對(duì)于任意gmH，有 m = qs+t，0ts， 由于gqs= (gs)qH（子群H的封閉性，q個(gè)gs連乘也屬于H），所以 gt = gm(gqs)1H， （gqs存在逆元，且由于封閉性，gm，

8、(gqs)1乘積屬于H）由于s是使gsH的最小正整數(shù)，因此得 t = 0，gm(gs)q H的任意元素都是gs的冪，則H = (gs,循環(huán)群群的結(jié)構(gòu)信息安全數(shù)學(xué),15,循環(huán)群與其子群,證明2）當(dāng)(g)是無(wú)限循環(huán)群時(shí)，如果n m，則gn gm，于是gms (m=0，1，2，)兩兩不同，H是無(wú)限循環(huán)群 證明3）假設(shè)(g)是n階循環(huán)群，由于n = qs+t，0ts，則e = gn = gqs+t， 于是 gt = (gqs)1H， s的最小性使得t = 0，所以 n = qs， H可表示為H = e，gs，g(q1)s 當(dāng)s = n時(shí)H = e,循環(huán)群群的結(jié)構(gòu)信息安全數(shù)學(xué),16,循環(huán)群與其子群,上頁(yè)

9、不僅證明了H的階q是n的正因子，而且給出n的正因子q階子群當(dāng)q跑遍n的所有正因子時(shí)，s也跑遍n的正因子，所以對(duì)于n的每一個(gè)正因子q，都有而且僅有一個(gè)q階循環(huán)子群,循環(huán)群群的結(jié)構(gòu)信息安全數(shù)學(xué),17,循環(huán)群與其子群,例3.1.38階循環(huán)群G的真子群 8的所有正因子為1，2，4，8相應(yīng)的子群分別為 e， e，g4， e，g2，g4，g6， G 其中e和G是群G的平凡子群,循環(huán)群群的結(jié)構(gòu)信息安全數(shù)學(xué),18,3.2 剩余類群,剩余類的概念： 根據(jù)同余的概念，我們可以將全體整數(shù)Z進(jìn)行分類：設(shè)m是正整數(shù)，把模m同余的整數(shù)歸為一類，即可表示為 a = qm+r， 0 r m，q = 0，1，2，的整數(shù)為一類，

10、稱為剩余類，剩余類中的每個(gè)數(shù)都稱為該類的剩余或代表，r稱為該類的最小非負(fù)剩余,循環(huán)群群的結(jié)構(gòu)信息安全數(shù)學(xué),19,剩余類群,例3.3.1m = 8，r = 5的剩余類為5，18+5，28+5，38+5， 這樣我們將全體整數(shù)按模m分成m個(gè)剩余類： 這m個(gè)剩余類可分別表示為： = 0，m，2m，3m，； = 1，1m，12m，13m，； = 2，2m，22m，23m，； = (m1)，(m1)m，(m1)2m，(m1)3m， 這m個(gè)剩余類稱為模m剩余類記為Zm,循環(huán)群群的結(jié)構(gòu)信息安全數(shù)學(xué),20,剩余類群,設(shè) 和 是兩個(gè)模m的剩余類，定義剩余類的加法如下： 如Z8的兩個(gè)剩余類 和,循環(huán)群群的結(jié)構(gòu)信息安

11、全數(shù)學(xué),21,剩余類群,定理3.2.1模m的全體剩余類集合對(duì)于剩余類加法構(gòu)成m階循環(huán)群 證明 封閉性和結(jié)合律顯然滿足 是單位元， 的逆元是 故剩余類集合是一個(gè)群該群是一個(gè)循環(huán)群，生成元是，注意對(duì)于加法，元素的“冪”就是元素的連加,循環(huán)群群的結(jié)構(gòu)信息安全數(shù)學(xué),22,剩余類群,定理3.2.2任意無(wú)限循環(huán)群與整數(shù)加群Z同構(gòu)，任意有限n階循環(huán)群與n階剩余類加群同構(gòu) 證明設(shè)(g)任意循環(huán)群 如果(g)是無(wú)限循環(huán)群，做整數(shù)加群Z到(g)的映射如下：對(duì)于任意kZ，有 f(k) = gk， 這是一個(gè)一一映射，而且對(duì)于k，hZ， f(k)f(h) = gkgh = gk+h = f(k+h) 故f是Z到(g)的

12、同構(gòu)映射，(g)與Z同構(gòu),循環(huán)群群的結(jié)構(gòu)信息安全數(shù)學(xué),23,剩余類群,證明續(xù)）如果(g)是n階循環(huán)群，做模m剩余類加群Zm到(g)的映射：對(duì)于任意 Zm， f( ) = gk， 這顯然是一一映射，而且對(duì)于， Zm ， f( )f( ) = gk gh = gk+h = f( ) 故f是Zm到(g)的同構(gòu)映射，(g)與Zm同構(gòu) 定理3.2.2的意義在于通過(guò)了解整數(shù)加群和剩余類加群，就了解了一切無(wú)限循環(huán)群和有限循環(huán)群的構(gòu)造,循環(huán)群群的結(jié)構(gòu)信息安全數(shù)學(xué),24,3.3 子群的陪集,引理設(shè)G是一個(gè)群 1）對(duì)于任意aG，集合 aG = ah | hG= G 2）GG = ah | hG，aG= G,循環(huán)群

13、群的結(jié)構(gòu)信息安全數(shù)學(xué),25,子群的陪集,證明1）a，h都是G的元素，由G的封閉性，我們有 ahG 則對(duì)于任意baG，總有bG，于是aG G 對(duì)于任意bG，我們有 b = eb = (aa1)b = a(a1b)， 由于a1bG， 所以 b = a(a1b)aG， 于是 G aG 故G = aG 2,循環(huán)群群的結(jié)構(gòu)信息安全數(shù)學(xué),26,子群的陪集,定義3.3.1設(shè)H是群G的一個(gè)子群對(duì)于任意aG，集合ah | hH 稱為H的一個(gè)左陪集，記為aH 同樣我們定義右陪集 Ha = ha | hH 對(duì)于交換群（阿貝爾群），左陪集和右陪集是一致的，可以稱為陪集,循環(huán)群群的結(jié)構(gòu)信息安全數(shù)學(xué),27,1） （2）

14、這說(shuō)明陪集中的任何元素均可以作為代表元。 （3）兩個(gè)陪集相等的條件 （4）對(duì)任何a，bG有aH=bH或 因而H的所有左陪集的集合aHa G構(gòu)成了G的劃分,陪集的性質(zhì),所有性質(zhì)對(duì)右陪集也成立,循環(huán)群群的結(jié)構(gòu)信息安全數(shù)學(xué),28,陪集的性質(zhì),證明： （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

15、1，h2H ,ah1=bh2，有 a-1b=h1h2-1 H ，反之，若a-1b H ，有b aH ,由（2）知，bH=aH,循環(huán)群群的結(jié)構(gòu)信息安全數(shù)學(xué),29,陪集的性質(zhì),4）任何a，b G，有，aH=bH或 這是因?yàn)槿绻?， 則存在 x aHbH ， 于是 x=ah1=bh2 ， 得a-1b=h1h2-1 H， 由性質(zhì)（3）知，aH=bH， 又因?yàn)槿魏我粋€(gè)元素a均可以作陪集aH，因而 ，所以aHa G是G的一個(gè)劃分,循環(huán)群群的結(jié)構(gòu)信息安全數(shù)學(xué),30,陪集的性質(zhì),陪集的性質(zhì)（4）整理成定理3.3.1 定理3.3.1設(shè)H是群G的一個(gè)子群H的任意兩個(gè)左（右）陪集或者相等或者無(wú)公共元素群G可以表示成

16、若干互不相交的左（右）陪集的并集,循環(huán)群群的結(jié)構(gòu)信息安全數(shù)學(xué),31,陪集的性質(zhì),例3.3.2設(shè)m是一個(gè)正整數(shù)，M表示所有m的倍數(shù)組成的集合，即M = mt | t = 0，1，2，3， = 0，m，2m，3m， M的另一種表示為M = mt | tZ 顯然M是整數(shù)加群Z的子群 設(shè)為模m的一個(gè)剩余類，即 于是我們有 可見(jiàn) 是M的一個(gè)陪集由Z可以按模m分成m個(gè)剩余類，則Z可以按M分成m個(gè)陪集： M，1+M，2+M，(m1)+M,循環(huán)群群的結(jié)構(gòu)信息安全數(shù)學(xué),32,子群的指數(shù)及Lagrange定理,下面我們討論兩個(gè)問(wèn)題： 1）陪集元素?cái)?shù)目是多少？ 2）陪集也可以成為子群?jiǎn)幔?引理：設(shè)G是群，H是G的子

17、群（HG），SL=aHaG， SR=aHaG，則存在SL到SR的雙射。 證明：作SL到SR的一個(gè)對(duì)應(yīng)關(guān)系 ：aH Ha-1（ SL SR ），因?yàn)?所以是映射且是單射。又對(duì)任意Ha SR，取a-1H SL，則 （ a-1H ）=Ha，所以也是滿射。即命題得證,循環(huán)群群的結(jié)構(gòu)信息安全數(shù)學(xué),33,子群的指數(shù)及Lagrange定理,集合SL和SR是等勢(shì)的，當(dāng)他們是有限集合時(shí)，左陪集的個(gè)數(shù)等于右陪集的個(gè)數(shù)： SL = SR ，稱為H在G中的指數(shù),記作G：H。 另外，從引理的證明中，我們不難發(fā)現(xiàn)，對(duì)于有限子群H，每個(gè)左（右）陪集內(nèi)元素?cái)?shù)目都等于H的階；即 aH = H ，且由于eH，則 ，即 H的其他陪

18、集中不含單位元e，所以它們不可能是群故H的陪集除H外對(duì)于G的運(yùn)算都不是群,循環(huán)群群的結(jié)構(gòu)信息安全數(shù)學(xué),34,子群的指數(shù)及Lagrange定理,推論1 （拉格朗日定理）設(shè)G是一個(gè)有限群，H是一個(gè)子群，則H的階是G的階的因子即 G= H G:H 推論2設(shè)G是一個(gè)有限群，G中的每一個(gè)元素的階一定是G的階的因子設(shè)G的階為n，則對(duì)任意aG，有an = e,推論1、2證明比較簡(jiǎn)單，請(qǐng)同學(xué)自己嘗試證明,循環(huán)群群的結(jié)構(gòu)信息安全數(shù)學(xué),35,子群的指數(shù)及Lagrange定理,推論3階為素?cái)?shù)的群一定為循環(huán)群 證明設(shè)群G的階為素?cái)?shù)，即|G|是素?cái)?shù) 當(dāng)|G| = 1時(shí)，群G是只含單位元e的循環(huán)群 當(dāng)|G| 1時(shí)，取aG

19、且a e， 則a生成一個(gè)循環(huán)子群H，且|H| 1由于|H|是|G|的的因子，而當(dāng)|G|是素?cái)?shù)時(shí)，它只有1和|G|兩個(gè)因子，故 |H| = |G|， 這表明H = G，G是一個(gè)循環(huán)群,循環(huán)群群的結(jié)構(gòu)信息安全數(shù)學(xué),36,3.4 正規(guī)子群、商群,定義3.4.1設(shè)H是群G的子群如果H的每一個(gè)左陪集也是右陪集，即對(duì)于任意aG，總有 aH = Ha， 則稱H為G的正規(guī)子群，或不變子群顯然阿貝爾群的所有子群是正規(guī)子群,循環(huán)群群的結(jié)構(gòu)信息安全數(shù)學(xué),37,正規(guī)子群,定理3.4.1設(shè)H是群G的子群則下面4個(gè)命題是等價(jià)的 1）H是群的正規(guī)子群； 2）對(duì)于任意aG，總有 aHa1 = H； 3）對(duì)于任意aG及任意hH

20、，總有 aha1H 4）對(duì)于任意aG，總有 aHa1H,循環(huán)群群的結(jié)構(gòu)信息安全數(shù)學(xué),38,正規(guī)子群,證明我們通過(guò)證明1)2)3)4)1)，從而證明4個(gè)命題等價(jià) 1)2)：如果H是正規(guī)子群，則 aHa1 = (aH) a1 = (Ha) a1 =H (aa1) = He = H 2)3)：顯然 3)4)：也是顯然 4)1)：由aHa1H，得aHHa；又由a1HaH（注意對(duì)于任意aG，有aHa1H，而a1G，所以a1HaH），得HaaH故 Ha = aH 定理證畢,定理3.4.1表明，子群是正規(guī)子群的充分必要條件是2或者3或者4,循環(huán)群群的結(jié)構(gòu)信息安全數(shù)學(xué),39,正規(guī)子群,定義3.4.2設(shè)A，B是群G中的兩個(gè)子集合，定義子集合A和B的乘積為 AB = ab | a，bG， 即為A中元素和B中元素相乘得到的集合 顯然子集乘積滿足結(jié)合律： (AB)C = A(BC) 如果A是一個(gè)子群，bG，令B = b，則G的左陪集bA可表示為BA,循環(huán)群群的結(jié)構(gòu)信息安全數(shù)學(xué),40,正規(guī)子群,定理3.4.2設(shè)H是群G的一個(gè)子群，H是正規(guī)子群的充分必要條件是任意兩個(gè)左（右）陪集的乘積仍然是一個(gè)左（右）陪集 證明如果H是正規(guī)子群，aH和bH是H的兩個(gè)左陪集，則 (aH)(bH) = a(Hb)H = a(bH)H = ab