《离散数学》练习题和参考答案

若a的阶是无限的，则类似于上述证明过程可以得出，h(a)的阶也是无限的。 故结论成立。

55、有限群G的每个元素的阶均能整除G的阶。 证明：

设|G|=n，?a?G，则|a|=m。令H={e,a,a2,…,am-1}。

则H是G的子群且|H|=m。由Lagrange定理知|H|能整除|G|，故a的阶能整除G的阶。 56、证明：在同构意义下，只有两个四阶群，且都是循环群。 证明：

在4阶群 G中，由Lagrange定理知，G中的元素的阶只能是1，2或4。阶为1 的元素恰有一个，就是单位元e. 若G有一个4阶元素，不妨设为a，则G=（a）,即G是循环群 ，从而是可交换群。

若G没有4阶元素，则除单位元e外，G的其余3个阶均为2。不妨记为a,b,c。因为a,b,c的阶均为2，故a-1=a,b-1=b,c-1=c。从而a?b?a, a?b?b, a?b?e,故a?b=c。同理可得a?c=c?a=b, c?b=b?c=a, b?a=c。 57、在一个群中，若G中的元素a的阶是k，即|a|=k，则a-1的阶也是k。 证明：

因为| a |=k，所以ak=e。即（a-1）k=(ak)-1=e。 从而a-1的阶是有限的，且|a-1|?k。 同理可证，a的阶小于等于|a-1|。 故a-1的阶也是k。

58、在一个群中，若A和B 都是G的子群。若A?B=G，则A=G或B=G。 证明： 用反证法证明。

若A?G且B?G，则有a?A,a?B且b?B,b?A。因为A，B都是G的子群，故a,b?G，从而a*b?G。 因为a?A,所以a

?1?A。若a*b?A,则b= a?1*(a*b)?A，这与a?B矛盾。从而a*b?A。

同理可证a*b?B。

综合可得a*b?A?B=G，这与已知矛盾。从而假设错误，得证A=G或B=G。 59、设e是奇数阶交换群的单位元，则G的所有元素之积为e。 证明：

设G=<{e,a1,a2,…,a2n},*>，n为正整数。

因为G的阶数为奇数2n+1，所以由拉格朗日定理知G中不存在2 阶元素，即除了单位元e以外，G的所有元素的阶都大于2。故对G中的任一非单位元a，它的逆元a

?1不是它本身，且G中不同的元素有不同的逆元。

由此可见，G中的2n个非单位元构成互为逆元的n对元素。因为G 是交换群，故G的所有元素之积可变成单位元和n对互为逆元的元素之积的积，从而结果为e。

60、设S=Q?Q，Q为有理数集合，*为S上的二元运算：对任意(a,b)，(c,d)?S,有 (a,b)*(c,d)=(ac,ad+b),

33

求出S关于二元运算*的单位元，以及当a?0时，(a,b)关于*的逆元。 解：

设S关于*的单位元为(a,b)。根据*和单位元的定义，对?(x,y)?S,有 (a,b)*(x,y)=(ax,ay+b)=(x,y), (x,y)*(a,b)=(ax,xb+y)=(x,y)。 即ax=x,ay+b=y,xb+y=y对?x,y?Q都成立。解得a=1,b=0。 所以S关于*的单位元为(1,0)。

当a?0时，设(a,b)关于*的逆元为(c,d)。根据逆元的定义，有 (a,b)*(c,d)= (ac,ad+b)=(1,0) (c,d)*(a,b)= (ac,cb+d)=(1,0)

1b即ac=1,ad+b=0,cb+d=0。解得c=a,d=-a。 1b 所以(a,b)关于*的逆元为(a,-a)。

61、设是一个群，H、K是其子群。定义G上的关系R：对任意a,b∈G，aRb ?存在 h∈H,k∈K, 使得b=h*a*k，则R是G上的等价关系。 证明：

?a∈G，因为H、K是G的子群，所以e∈H且e∈K。令h=k=e,则a=e*a*a=h*e*k,从而aRa。即R是自反的。 ?a,b∈G，若aRb，则存在 h∈H，k∈K, 使得b=h*a*k。因为H、K是G的子群，所以h-1∈H且k-1∈K。故a=h-1*a*k-1,

从而bRa。即R是对称的。

?a,b,c∈G，若aRb,bRc,则存在 h,g∈H，k,l∈K, 使得b=h*a*k，c=g*b*l。所以c=g*b*l=g*(h*a*k)*l=(g*h)*a*(k*l)。

因为H、K是G的子群，所以g*h∈H且k*l∈K。从而aRc。即R是传递的。 综上所述，R是G上的等价关系。 62、设H是G的子群，则下列条件等价： （1） H是G的不变子群； （2） ?a∈G，a?H?a-1?H； （3） ?a∈G，a-1?H?a?H；

（4） ?a∈G，?h∈G，a?h?a-1?H。 证明：

(1)?(2) ?a∈G，则对h∈H,令h1=a?h?a-1，因为a?h ? a?H且H?a=a?H，所以?h2∈H，使得a?h=h2?a。故h1=（h2?a）?a-1=h2?H。故 a?H?a-1?H。

(2)?(3) ?a∈G，对h∈H,令h1=a-1?h?a，则（h1）-1= a?h-1?a-1。因为h-1∈H，所以（h1）-1= a?h-1?a-1∈a?H?a-1。由（2）可知（h1）-1∈H,从而h1?H。故a-1?H?a?H 。 (3)?(4) 类似于（2）?(3)的证明。

(4)?(1) ?a∈G，对?b∈a?H，则?h∈H，使得b=a?h。故b=(a?h) ?(a-1?a)=(a?h?a-1)?a。由于a?h?a-1

34

∈H，所以b∈H?a。即a?H?H?a。

反之对?b∈H?a，则?h∈H，使得b=h?a。故b=(a?a-1) ?(h?a)=a?(a-1?h?a)=a?(a-1?h?(a-1)-1)。由于a-1?h?(a-1)-1∈H，所以b∈a?H。即H?a?a?H。 即H?a=a?H。从而H是G的不变子群。

63、在半群中，若对?a,b?G，方程a*x=b 和y*a=b都有惟一解，则是一个群。 证明：

任意取定a?G，记方程a*x=a的惟一解为eR。即a*eR=a。 下证eR为关于运算*的右单位元。 对?b?G，记方程y*a=b的惟一解为y。

?是半群，?运算*满足结合律。 ?b*eR=(y*a)*eR=y*(a*eR)=y*a=b。

类似地，记方程y*a=a的唯一解为eL。即eL*a=a。 下证eL为关于运算*的左单位元。 对?b?G，记方程a*x=b的惟一解为x。

?是半群，?运算*满足结合律。 ?eL*b=eL*(a*x)=(eL*a)*x=a*x=b。

从而在半群中, 关于运算*存在单位元，记为e。 现证G中每个元素关于运算*存在逆元。

对?b?G，记c为方程b*x=e的惟一解。下证c为b关于运算的逆元。记d=c*b。 则b*d=(b*c)*b=e*b=b。

?b*e=b,且方程b*x=b有惟一解，?d=e。 ?b*c=c*b=e。从而c为b关于运算的逆元。

综上所述，是一个群。

64、设是群， H和K都是G的子群，令HK={h*s | s∈K，h∈H}, KH={s*h |s∈K,h∈H},，是G的子群的充分必要条件是HK=KH。 证明：

?HK是G的子群。?c?HK，则c-1?HK，故存在a?H,b?K ,使得c-1=a·b。因为c=（a·b）-1=b-1·a-1。因为H

和K都是G 的子群，所以a-1?H,b-1?K ，即c?KH。从而HK?KH。 ?c?KH，则存在a?H,b?K ,使得c=b·a。因为c=（a-1·b-1）-1。因为H和K都是G 的子群，所以a-1?H,b-1?K ，即a-1·b-1?HK。因为HK是G的子群，所以c=（a-1·b-1）-1?HK。从而KH?HK。 故HK=KH。

?HK=KH。对?c，d?HK，有a1,a2?H,b1,b2?K ,使得c=a1·b1 ,d=a2·b2。则

c·d=( a1·b1)·(a2·b2)=(( a1·b1)·a2)·b2=( a1·(b1·a2))·b2。因为b1·a2?KH=KH，所以存在a3?H,b3?K ,使得b1·a2 =a3·b3。从而c·d=( a1·（b1·a2）·b2=(a1·（a3·b3）)·b2=(a1·a3)·(b3·b2)。因为H和K都是G的子群，故a1·a3?H, b3·b2?K。从而c·d?HK。

35

又c-1=(a1·b1)-1=b-11·a-11。因为H和K都是G的子群，故a-11?H, b-11?K。从而c-1?KH。因为HK=KH，所以c-1?HK。

综上所述，HK是G的子群。

65、设H和K都 是G的不变子群。证明：HK也是G 的不变子群。 证明：

先证HK是G 的子群。

对?a?HK，有hH，k?K，使得a=h·k。因为a=h·k=(h·k·h-1)·h，且K是G 的不变子群，所以h·k·h-1K。故a?KH。从而HK?KH。 同理可证，KH?HK。

故HK=KH。从而HK是G的子群。 下证HK是G的不变子群。

对?a?G，b?HK，有hH，k?K，使得b=h·k。故a·b·a-1=a·(h·k)·a-1=(a·h·a-1)·(a·k·a-1)。因为H和K都是G的不变子群，所以a·h·a-1?H且a·k·a-1?K。从而a·b·a-1?HK。故HK是G 的不变子群。 66、设为群，a,b,c?G。若a*b=c*b*a,a*c=c*a,b*c=c*b，且a,b的阶分别为m,n，则c的阶整除m与n的最大公因子(m,n)。 证明：

设c的阶为k。在a*b=c*b*a两边同时右乘ba*b=(c*b*a)*b=(c*b)*a*b=(c*b)*a*b

32n?2n?3

nn?1n?1???，再由a*b=c*b*a得

n?2n?3

=(c*b)*(a*b)*b

2n?2=(c*b)*(c*b*a)*b

2

=(c*b)*(a*b)*b=…=(c*b)*a,

nn?3

=(c*b)*(c*b*a)*b

再由b*c=c*b及b 的阶为n得

a=a*b= (c*b)*a=(c*b)*a=c*a, 所以c=e。故由元素阶的定义有k|n。

由a*b=c*b*a,a*c=c*a,b*c=c*b得a*b=b*a*c，两边同时左乘aa*b=a= a= a

m?2m?3mm?1m?1nnnnnn，再由a*b=b*a*c得

*(b*a*c)= a

2m?2* (a*b)*(a*c)= a

2m?2*(b*a*c)*(a*c)

2*b*(a*c)= a

3m?3*(a*b)*(a*c)= a

mm?3*(b*a*c)*(a*c)

*b*(a*c)=…=b*(a*c),

再由a*c=c*a及a 的阶为m得

b= a*b= b*(a*c)=b* a * c=b*c, 所以c=e。故由元素阶的定义有k|m。

由此可见，k是m和n的公因子，从而能整除m和n的最大公因子(m,n)。

36

mmmmmm