组合数学第四版卢开澄标准答案-第四章

《组合数学第四版卢开澄标准答案-第四章》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、习题四4.1.若群G的元素a均可表示为某一元素x的幂，即a=xm，则称这个群为循环群。若群的元素交换律成立，即a,bÎG满足a×b=b×a则称这个群为阿贝尔(Abel)群，试证明所有的循环群都是阿贝尔群。[证].设循环群(G,×)的生成元是x0ÎG。于是，对任何元素a,bÎG，$m，nÎN，使得a=x0m,b=x0n,从而a×b=x0m×x0n=x0m+n(指数律)=x0n+m(数的加法交换律)=x0n×x0m　　(指数律)=b×a故×运算满足交换律；即(G,×)是交换群。4.2.若x是群G的一个元素，存

2、在一个最小的正整数m，使xm=e，则称m为x的阶，试证：C={e,x,x2,¼,xm-1}是G的一个子群。[证].(1)非空性C¹Æ：因为$eÎG；(2)包含性CÍG：因为xÎG，根据群G的封闭性，可知x2,¼,xm-1,(xm=)eÎG，故CÍG；(3)封闭性"a,bÎCÞa×bÎC："a,bÎC，$k，lÎN(0£k

3、m)，使a=xk,从而a-1=xm-kÎC(因为0£m-k

4、C

5、£

6、G

7、=n所以群G的所有元素的阶都不超过n。4.4.若G是阶为n的循环群，求群G的母元素的数目，即G的元素可以表示成a的幂：a,a2,¼,an的元

8、素a的数目。[证].设(G,×)是循环群，a是其一个母元素(生成元)，a的阶为n(也是G的阶)，则G={a,a2,¼,an(=e)}。(1).我们来证：对任何自然数rÎN(0

9、r×k。已知0

10、k，所以n£k。其次，(ar)n=ar×n(指数律)=an×r(数的加法交换律)=(an)r

11、(指数律)=er=e。因而，由k是元素ar的阶，具有最小性，所以k£n。【第9页共9页】综合这两方面，可得k=n。(2).根据(1)的结论，可得，群G的母元素的数目为j(n)(欧拉函数，小于n且与n互素的数的个数)。注.引理*.设(G,×)是群。"xÎG，若x的阶为k，从而xk=e。则"mÎN,xm＝eÛk

12、m。[证].先证Þ)：　若xm＝e，则必有k

13、m。　否则k∤m，于是，由带余除法，可设m=kq+r(0

14、指数律)＝e×e-q(xm＝e,xk=e)＝e×e＝e　故与x的阶为k，具有最小性，矛盾。次证Ü):若k

15、m，则m=kq。于是xm＝xkq＝(xk)q(指数律)＝eq(xk=e)=e。4.5.试证循环群G的子群仍是循环群。[证].设(H,×)是循环群(G,×)=的一个子群，则H中的元素都可表示成a的一些正方幂。设am是H中指数最小的正方幂，我们来证(H,×)=。为此只要证明H中任一元素都可表示成am的正方幂即可。任取H中一个元素ak，根据带余除法，可知有非负整数q及r，使k=qm+r且0£r

16、，因而(H,×)循环群。4.6.若H是G的子群，x和y是G的元素，试证xHÇyH或为空，或xH=yH。[证].对任何x,yÎG，若xHÇyH=Æ，则问题已证。否则若xHÇyH¹Æ，则必至少有一元素x0ÎxHÇyH，从而x0ÎxHÇyHÞx0ÎxHÙx0ÎyH　　Þx0=x×h1Ùx0=y×h2(这里h1,h2ÎH)Þx×h1

17、=y×h2Þx=y×h2×h1-1Ùy=x×h1×h2–1(*)下面我们来证：xH=yH。为此，要分证：(1)xHÍyH；(2)yHÍxH；我们只证(1)；(2)同理可证；对任何元素a，aÎxHÞa=x×h¢(这里h¢ÎH)Þa=y×h2×h1-1×h¢(由(*)：x=y×h2×h1-1)Þa=y×h¢¢(由H的封闭性：h¢¢=h2×h1-1×h¢ÎH)ÞaÎyH【第9页共9页】所以xHÍyH；所以，由包含关系的反对称性，我们