组合数学第四版卢开澄标准答案-第四章精品资料 下载本文

内容发布更新时间 : 2024/5/1 19:51:13星期一 下面是文章的全部内容请认真阅读。

习 题 四

4.1. 若群G的元素a均可表示为某一元素x的幂,即a = xm,则称这个群为循环群。若群的元素交换律成立,即a , b G满足 ab = ba

则称这个群为阿贝尔(Abel)群,试证明所有的循环群都是阿贝尔群。

[证].设循环群(G, )的生成元是x0?G 。于是,对任何元素a , b G,m,n?N,使得a= x0m , b= x0n ,从而 ab = x0m x0n

= x0m +n (指数律)

= x0n +m (数的加法交换律)

= x0n x0m (指数律) = ba

故 运算满足交换律;即(G, )是交换群。

4.2. 若x是群G的一个元素,存在一个最小的正整数m,使xm=e,则称m为x的阶,试证:

2m-1

C={e,x,x, ,x} 是G的一个子群。 [证].(1)非空性C :因为e?G;

(2)包含性CG:因为x ?G,根据群G的封闭性,可知x2, ,xm-1, (xm=)e?G,故CG;

(3)封闭性a , b C a b C: a , b C,k,l?N (0 k

使a = x , b = x,从而

a b = xk xl = x(k+l) mod mC (因为0 (k+l) mod m < m) ;

(4)有逆元a C a -1C: a C,k ?N (0 k

a -1 = xm-kC (因为0 m-k < m) 。

综合(1) (2) (3) (4),可知(C, )是(G, )的一个子群。

4.3. 若G是阶为n的有限群,则G的所有元素的阶都不超过n。 [证].对任一元素x?G,设其阶为m,并令C={e,x,x2, ,xm-1},则由习题4.2.可知(C, )是(G, )的一个子群,故具有包含性CG。因此有

m = |C| ? | G | = n

所以群G的所有元素的阶都不超过n。

4.4. 若G是阶为n的循环群,求群G的母元素的数目,即G的元素可以表示成a的幂: a,a2, ,an 的元素a的数目。

[证].设(G, )是循环群,a是其一个母元素(生成元),a的阶为n(也是G的阶),则

G ={a,a2, ,an(=e) }。

(1).我们来证:对任何自然数r ?N (0< r

为此,只需证ar的阶为n即可。

首先,设ar的阶为k,因此有ark = (ar)k = e,由于a的阶为n,故根据引理*可得n | rk 。已知0< r

(ar)n = arn (指数律)

= anr (数的加法交换律) =(an)r (指数律)

= er = e 。

因而,由k是元素ar的阶,具有最小性,所以k n。

综合这两方面,可得k = n。

(2).根据(1)的结论,可得,群G的母元素的数目为(n) (欧拉函数,小于n且与n互素的数的个数)。

注.引理*.设(G,)是群。?x?G,若x的阶为k,从而xk =e 。则 ?m?N, xm=e ? k | m 。 [证].先证?):

若xm=e,则必有k | m 。

否则k ? m ,于是,由带余除法,可设 m=kq+r (0? r? k),故可得 r=m-kq,从而 xr=xm-kq =xm+(-kq)

=xm (xk)-q (指数律) =e e-q (xm=e, xk =e) =e e =e

故与x的阶为k,具有最小性,矛盾。 次证?):

若k | 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 且 0r

于是由(H, )构成群,可知(am)qH,从而(am)-qH,于是

ar=ak (am)-qH

由m的选择(最小性)必须有r=0,所以ak=(am)q,这说明(H, )=,因而(H, )循环群。

4.6. 若H是G的子群,x和y是G的元素,试证xHyH或为空,或xH = yH。 [证].对任何x,y?G,若xH ? yH=?,则问题已证。

否则若xH ? yH??,则必至少有一元素x0?xH ? yH,从而

x0? xH ? yH

? x0? xH ? x0? yH

? x0=xh1 ? x0 =yh2 (这里h1, h2?H) ? xh1 = yh2

? x = y h2h1-1 ? y = x h1h2–1 (*)

下面我们来证:xH = yH。为此,要分证: (1)xH ? yH ; (2)yH ? xH ;

我们只证(1) ;(2)同理可证 ;

对任何元素a, a? xH

? a =xh? (这里h??H)

? a = y h2h1-1h? (由(*):x = y h2h1-1 )

? a =y h?? (由H的封闭性 : h??= h2h1-1h??H) ? a? yH 所以 xH ? yH;

所以,由包含关系的反对称性,我们得到 xH = yH 。

4.7. 若H是G的子群,|H|=k,试证: |xH|=k 其中xG。

[证].建立自然映射 f : H?xH,使得 对任何h?H, f(h)=xh。于是 (1)后者唯一:由运算的结果唯一性可得;

(2)满射:对任何 b?xH,有a = h?H,使得b = xh。于是,有

f(a)= f(h)= xh = b ;

(3)单射: f(h1)= f(h2) ? xh1 = xh2

? h1 = h2 (群的消去律 )。

所以,f是从H到的双射,因此 |xH|=|H|=k 。

4.8.有限群G的阶为n,H是G的子群,则H的阶必除尽G的阶。

[证].这即是著名的拉格郎日(Lagrange法国著名数学家、力学家1736-1814)定理。

设G的子群H?{e,h1,h2,?,hr?1}。

于是令aH?{a?e?a,a?h1,a?h2,?,a?hr?1},这里a?G,并且我们定义R是G上的二元关系,即R?G?G

x,y?G,xRy::?(?b?G)(x?aH?y?aH)。

从而R是G上的等价关系,其等价块的形式为aH,设其代表元为a1,a2,?,ak,则

a1H,a2H,?,akH是所有的等价块,构成对G的一个划分(参见习题4.6.)。即

?a2H?????akH G?a1H?根据习题4.7.可得a1H?a2H???akH?H?r。

因此G?kH?kr?n,所以r必能整除n,即H的阶必除尽G的阶。

4.10. 若x和y在群G作用下属于同一等价类,则x所属的等价类Ex,y所属的等价类Ey有

|Ex| = |Ey| 。

[证].设底基X={1,2,,n}。对任一个元素a?X,Ea ={b?X | p?G , (a)p=b}。

因为已知x和y在群G作用下属于同一等价类,因此,存在z?X,使得x, y?Ez,于是p1, p2?G , 使得 (z)p1=x, (z)p2=y 。

我们来证:Ex = Ey 。为此,要分证: (1) Ex ? Ey ; (2) Ey ? Ex ;

我们只证(1) ;(2)同理可证 ;

对任何元素a?X, a? Ex

? a = (x)p? (这里p??G) ? a = (z)p1p? (由 (z)p1=x )

? a = (y)p2-1p1p? (由(z)p2=y , 得 (y)p2-1=z (群G有逆元))

? a = (y) p?? (由群G的封闭性 : p??= p2-1p1p??G)