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

第三章循環(huán)群、群的結(jié)構(gòu)3.1循環(huán)群（重要）3.2剩余類群（掌握）3.3子群的陪集（掌握）3.4正規(guī)子群、商群（重要）第1頁/共44頁第一頁，共45頁。3.1循環(huán)群定義3.1.1如果一個(gè)群G里的元素都是某一個(gè)元素g的冪，則G稱為循環(huán)群，g稱為G的一個(gè)生成元．由g生成的循環(huán)群記為(g)．無限循環(huán)群可表示為：{…，g2，g1，g0，g1，g2，…}，其中g(shù)0=e．有限n階循環(huán)群可表示為：{g0，g1，g2，…，gn1}，其中g(shù)0=e

第2頁/共44頁第二頁，共45頁。3.1循環(huán)群例3.1.1

整數(shù)加法群Z是一個(gè)循環(huán)群．1是生成元，每一個(gè)元素都是1的“冪”．這里再次說明我們討論的群里“乘法”是抽象的，只代表一種代數(shù)運(yùn)算．在整數(shù)加群中，“乘法”就是普通加法，那么“冪”就是一個(gè)元素的連加，例如1m＝m=，1m＝m=．而且規(guī)定0=10，即0為0個(gè)1相加．第3頁/共44頁第三頁，共45頁。循環(huán)群簡單性質(zhì)由n階循環(huán)群中g(shù)n=e，我們可以得到：設(shè)i，j是任意整數(shù)，1）如果i

j(modn)，則gi=gj．2）gi的逆元gi=gni．3）是交換群4）gn=e第4頁/共44頁第四頁，共45頁。循環(huán)群簡單性質(zhì)對于循環(huán)群G中兩個(gè)任意元gigj=gi+j

=gj+i=gjgi，所以循環(huán)群一定滿足交換律，是交換群（Abel群）．在n階循環(huán)群中，有g(shù)n=e．因?yàn)槿绻鹓n

e，假設(shè)gn=gi(0in1)，則由消去律得gni=e(0nin1)，這與n階循環(huán)群的定義矛盾．循環(huán)群是交換群第5頁/共44頁第五頁，共45頁。元素的階及其性質(zhì)1）a的所有冪兩兩不相等，于是以a為生成元的循環(huán)群{…，a2，a1，a0=e，a1，a2，…}是無限循環(huán)群．2）存在整數(shù)ij，使ai=aj，則aij=e．這表明存在正整數(shù)k=ij使ak=e．我們稱使上式成立的最小正整數(shù)n稱為元素a的階．在第1種情況下，這樣的正整數(shù)不存在，稱a是無限階元素．第6頁/共44頁第六頁，共45頁。元素的階及其性質(zhì)a是n階元素，則序列a0

（=e），a1，a2，…，an1兩兩不相同，而且a的一切冪都包含在這個(gè)序列中。證明：（反證法）如果ai

=aj，0j

i

n1，則aij=e，而0ij

n1，這與a是n階元素矛盾．對于任意整數(shù)m，am都包含在上面的序列中．m可表示為：m=qn+r，0rn，于是am=aqn

+r=(aq)nar=ar，因?yàn)閍r在上面的序列中，則am也在上面的序列中第7頁/共44頁第七頁，共45頁。元素的階及其性質(zhì)定理3.1.1

一個(gè)群G的任意元素a都能生成一個(gè)循環(huán)群，它是G的子群．如果a是無限階元素，則a生成無限循環(huán)群；如果a是n階元素，則a生成n階循環(huán)群．證明設(shè)a的冪集合為S．1）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=ai+jS，由定理2.2.3，S是G的子群．顯然S是a生成的循環(huán)群．定理證畢．顯然無限循環(huán)群的元素都是無限階元素．有限循環(huán)群生成元的階就是群的階．

第8頁/共44頁第八頁，共45頁。元素的階及其性質(zhì)定理3.1.2對于n階元素a有1）ai=e，當(dāng)且僅當(dāng)ni．2）ak的階為．證明

n階元素a生成n階循環(huán)群：{a0=e，a1，a2，…，an1}．1）由于ni，則i

0(modn)，于是ai=a0=e．反之，由i=qn+r，0rn，得ai=aqn+r=(an)qar=ear=ar=e，而n是使ak=e的最小正整數(shù)，所以r=0，故ni．第9頁/共44頁第九頁，共45頁。元素的階及其性質(zhì)2）設(shè)l=．由于(k，n)k，則于是由1）有(ak)l

=akl=e．而如果(ak)i=aki=e，則nki，因?yàn)樗怨适鞘?ak)i=e，成立的最小正整數(shù)．證畢．第10頁/共44頁第十頁，共45頁。元素的階及其性質(zhì)由定理3.1.2我們可以直接得出推論由元素g生成的n階循環(huán)群G中任意元素gk(0kn1)的階為，當(dāng)k，n互素時(shí)，gk的階為n，也是G的生成元．例3.1.2

8階循環(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)—?dú)W拉函數(shù)，以后我們還要深入討論），因此n階循環(huán)群共有(n)個(gè)n階元素或(n)個(gè)生成元．第11頁/共44頁第十一頁，共45頁。循環(huán)群與其子群定理3.1.3

1）循環(huán)群的子群是循環(huán)群，它或者僅由單位元構(gòu)成，或者由子群中具有最小正指數(shù)的元素生成，即生成元為具有最小正指數(shù)的元素；2）無限循環(huán)群的子群除{e}外都是無限循環(huán)群；3）有限n階循環(huán)群的子群的階是n的正因子，且對n的每一個(gè)正因子q，有且僅有一個(gè)q階子群．第12頁/共44頁第十二頁，共45頁。循環(huán)群與其子群證明1）

設(shè)H是循環(huán)群(g)的一個(gè)子群．假設(shè)H＝{e}，H自然是循環(huán)群．假設(shè)H{e}，則有i0使giH，又因?yàn)間i=(gi)1H，所以可以假定i0，說明有正指數(shù)存在．設(shè)s是H中的最小正指數(shù)，即s是使gsH的最小正整數(shù)，我們現(xiàn)在證明H=(gs)．對于任意gmH，有m=qs+t，0ts，由于gqs=(gs)qH（子群H的封閉性，q個(gè)gs連乘也屬于H），所以gt=gm(gqs)1H，（gqs存在逆元，且由于封閉性，gm，(gqs)1乘積屬于H．）由于s是使gsH的最小正整數(shù)，因此得t=0，gm＝(gs)q．H的任意元素都是gs的冪，則H=(gs)．第13頁/共44頁第十三頁，共45頁。循環(huán)群與其子群證明2）當(dāng)(g)是無限循環(huán)群時(shí)，如果n

m，則gn

gm，于是gms(m=0，1，2，…)兩兩不同，H是無限循環(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}．第14頁/共44頁第十四頁，共45頁。循環(huán)群與其子群

上頁不僅證明了H的階q是n的正因子，而且給出n的正因子q階子群．當(dāng)q跑遍n的所有正因子時(shí)，s也跑遍n的正因子，所以對于n的每一個(gè)正因子q，都有而且僅有一個(gè)q階循環(huán)子群．第15頁/共44頁第十五頁，共45頁。循環(huán)群與其子群例3.1.3

8階循環(huán)群G的真子群．8的所有正因子為1，2，4，8相應(yīng)的子群分別為{e}，

{e，g4}，{e，g2，g4，g6}，G其中{e}和G是群G的平凡子群第16頁/共44頁第十六頁，共45頁。3.2剩余類群剩余類的概念：根據(jù)同余的概念，我們可以將全體整數(shù)Z進(jìn)行分類：設(shè)m是正整數(shù)，把模m同余的整數(shù)歸為一類，即可表示為a=qm+r，0

r

m，q=0，1，2，…的整數(shù)為一類，稱為剩余類，剩余類中的每個(gè)數(shù)都稱為該類的剩余或代表，r稱為該類的最小非負(fù)剩余．第17頁/共44頁第十七頁，共45頁。剩余類群例3.3.1

m=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第18頁/共44頁第十八頁，共45頁。剩余類群設(shè)和是兩個(gè)模m的剩余類，定義剩余類的加法如下：如Z8的兩個(gè)剩余類

和

第19頁/共44頁第十九頁，共45頁。剩余類群定理3.2.1

模m的全體剩余類集合對于剩余類加法構(gòu)成m階循環(huán)群．證明封閉性和結(jié)合律顯然滿足．是單位元，的逆元是故剩余類集合是一個(gè)群．該群是一個(gè)循環(huán)群，生成元是，注意對于加法，元素的“冪”就是元素的連加．第20頁/共44頁第二十頁，共45頁。剩余類群定理3.2.2任意無限循環(huán)群與整數(shù)加群Z同構(gòu)，任意有限n階循環(huán)群與n階剩余類加群同構(gòu)．證明設(shè)(g)任意循環(huán)群．如果(g)是無限循環(huán)群，做整數(shù)加群Z到(g)的映射如下：對于任意kZ，有f(k)=gk，這是一個(gè)一一映射，而且對于k，hZ，f(k)f(h)=gkgh

=gk+h=f(k+h)．故f是Z到(g)的同構(gòu)映射，(g)與Z同構(gòu)．第21頁/共44頁第二十一頁，共45頁。剩余類群（證明續(xù)）如果(g)是n階循環(huán)群，做模m剩余類加群Zm到(g)的映射：對于任意Zm，f()=gk，這顯然是一一映射，而且對于，Zm

，f()f()=gkgh=gk+h=f()．故f是Zm到(g)的同構(gòu)映射，(g)與Zm同構(gòu)．定理3.2.2的意義在于通過了解整數(shù)加群和剩余類加群，就了解了一切無限循環(huán)群和有限循環(huán)群的構(gòu)造第22頁/共44頁第二十二頁，共45頁。3.3子群的陪集引理設(shè)G是一個(gè)群．1）對于任意aG，集合aG={ah|hG}=G．2）GG={ah|hG，aG}=G．第23頁/共44頁第二十三頁，共45頁。子群的陪集證明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=aG．2）第24頁/共44頁第二十四頁，共45頁。子群的陪集定義3.3.1設(shè)H是群G的一個(gè)子群．對于任意aG，集合{ah|hH}稱為H的一個(gè)左陪集，記為aH．同樣我們定義右陪集Ha={ha|hH}．對于交換群（阿貝爾群），左陪集和右陪集是一致的，可以稱為陪集．第25頁/共44頁第二十五頁，共45頁。（1）（2）這說明陪集中的任何元素均可以作為代表元。（3）兩個(gè)陪集相等的條件（4）對任何a，b∈G有aH=bH或因而H的所有左陪集的集合{aH︱a∈G}構(gòu)成了G的劃分。陪集的性質(zhì)所有性質(zhì)對右陪集也成立第26頁/共44頁第二十六頁，共45頁。陪集的性質(zhì)證明：（1）若a∈H，aH={ah︱h∈H}，顯然有aH=H;反之，若aH=H，即任意h∈H，有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，h1，h2∈H

）（3）若aH=bH，則存在h1，h2∈H,ah1=bh2，有a-1b=h1h2-1∈H

，反之，若a-1b∈H

，有b∈aH,由（2）知，bH=aH第27頁/共44頁第二十七頁，共45頁。陪集的性質(zhì)（4）任何a，b∈G，有，aH=bH或這是因?yàn)槿绻?，則存在x∈aH∩bH，于是x=ah1=bh2

，得a-1b=h1h2-1∈H，由性質(zhì)（3）知，aH=bH，又因?yàn)槿魏我粋€(gè)元素a均可以作陪集aH，因而，所以{aH︱a∈G}是G的一個(gè)劃分。第28頁/共44頁第二十八頁，共45頁。陪集的性質(zhì)陪集的性質(zhì)（4）整理成定理3.3.1定理3.3.1

設(shè)H是群G的一個(gè)子群．H的任意兩個(gè)左（右）陪集或者相等或者無公共元素．群G可以表示成若干互不相交的左（右）陪集的并集．第29頁/共44頁第二十九頁，共45頁。陪集的性質(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è)剩余類，即于是我們有可見是M的一個(gè)陪集．由Z可以按模m分成m個(gè)剩余類，則Z可以按M分成m個(gè)陪集：M，1+M，2+M，…，(m1)+M．第30頁/共44頁第三十頁，共45頁。子群的指數(shù)及Lagrange定理下面我們討論兩個(gè)問題：1）陪集元素?cái)?shù)目是多少？2）陪集也可以成為子群嗎？引理：設(shè)G是群，H是G的子群（H≤G），SL={aH︱a∈G}，SR={aH︱a∈G}，則存在SL到SR的雙射。證明：作SL到SR的一個(gè)對應(yīng)關(guān)系Ψ：aHHa-1（SL→SR

），因?yàn)樗驭肥怯成淝沂菃紊?。又對任意Ha∈SR，取a-1H∈SL，則Ψ（a-1H

）=Ha，所以Ψ也是滿射。即命題得證。第31頁/共44頁第三十一頁，共45頁。子群的指數(shù)及Lagrange定理集合SL和SR是等勢的，當(dāng)他們是有限集合時(shí)，左陪集的個(gè)數(shù)等于右陪集的個(gè)數(shù)：︱SL︱=︱SR︱，稱為H在G中的指數(shù),記作[G：H]。另外，從引理的證明中，我們不難發(fā)現(xiàn)，對于有限子群H，每個(gè)左（右）陪集內(nèi)元素?cái)?shù)目都等于H的階；即︱aH︱=︱H︱，且由于e∈H，則，即H的其他陪集中不含單位元e，所以它們不可能是群．故H的陪集除H外對于G的運(yùn)算都不是群．第32頁/共44頁第三十二頁，共45頁。子群的指數(shù)及Lagrange定理推論1

（拉格朗日定理）設(shè)G是一個(gè)有限群，H是一個(gè)子群，則H的階是G的階的因子．即︱G︱=︱H︱[G:H]推論2設(shè)G是一個(gè)有限群，G中的每一個(gè)元素的階一定是G的階的因子．設(shè)G的階為n，則對任意aG，有an

=e．推論1、2證明比較簡單，請同學(xué)自己嘗試證明第33頁/共44頁第三十三頁，共45頁。子群的指數(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且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)群．第34頁/共44頁第三十四頁，共45頁。3.4正規(guī)子群、商群定義3.4.1設(shè)H是群G的子群．如果H的每一個(gè)左陪集也是右陪集，即對于任意aG，總有aH=Ha，則稱H為G的正規(guī)子群，或不變子群．顯然阿貝爾群的所有子群是正規(guī)子群．第35頁/共44頁第三十五頁，共45頁。正規(guī)子群定理3.4.1設(shè)H是群G的子群．則下面4個(gè)命題是等價(jià)的．1）H是群的正規(guī)子群；2）對于任意aG，總有aHa1=H；3）對于任意aG及任意hH，總有aha1H．4）對于任意aG，總有aHa1H．第36頁/共44頁第三十六頁，共45頁。正規(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（注意對于任意aG，有aHa1H，而a1G，所以a1HaH），得HaaH．故Ha=aH．定理證畢．定理3.4.1表明，子群是正規(guī)子群的充分必要條件是2或者3或者4．第37頁/共44頁第三十七頁，共45頁。正規(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=，則G的左陪集bA可表示為BA．第38頁/共44頁第三十八頁，共45頁。正規(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=abH．反之，如果(aH)(bH)是一陪集，假設(shè)(aH)(bH)=cH．因?yàn)閑HaaH和bbH，則ab(aH)(bH)=cH，第39頁/共44