信息安全数学基础答案第一二三四五章(许春香 廖永建)

1、第一章1、 5,4,1,5.2、 100=22*52, 3288=23*3*137.4、 a,b可以表示成多个素因子的乘积a=p1p2pr, b=q1q2qs,又因为(a, b)=1，表明a, b没有公共(相同)素因子. 同样可以将an, bn表示为多个素因子相乘an=(p1p2pr)n, bn=(q1q2qs)n明显an, bn也没有公共(相同)素因子.证明：由于（a,b）=1，由互素性质3（如果（a,c）=1 （b,c）=1,则 （ab,c）=1）得 （a2,b）=1，因此得 （an, b）=1 ，同理得 （an, bn）=1.5、 同样将a, b可以表示成多个素因子的乘积a=p1p2pr

2、, b=q1q2qs, an=(p1p2pr)n, bn=(q1q2qs)n,因为an| bn所以对任意的i有, pi的n次方| bn, 所以bn中必然含有a的所有素因子, 所以b中必然含有a的所有素因子, 所以a|b.证明：设a=q1q2qr, b=p1p2ps, 其中qi, pj 为素数。 因为anbn，所以abnq1q2qr p1np2nps n又由定理1（page7），存在j1满足 q1 pj1n又因为pj 为素数，所以有 q1 = pj1同理得q2 = pj2 , qr = pjr,得 a= q1q2qr =pj1 pj2 pjr p1p2ps = b .注意：在证明过程没使用标准因

3、子分解式！6、 因为非零a, b, c互素,所以(a, b)=(a, c)=1,又因为a=p1p2pr, b=q1q2qs, ab=p1p2prq1q2qs, 又因为a, b, c互素, 所以a, b, c中没有公共(相同)素因子, 明显ab和c也没有公共(相同)素因子.所以(ab, c)= (a, b)(a, c).定义：（1）如果整数dai (1 i n) ,则d称为ai的公因子（2）设d0是ai (1 i n)的公因子，如果ai (1 i n) 的任何公因子都整除d，则d称为ai (1 i n)的最大公因子，记为d= (a1,an)（3）如果d = 1, 则称整数a1 , an 互素。注

4、意：（1）整数a , b 互素的充要条件存在整数 s,t 满足 sa+tb=1. s, t是否唯一？（2）整数a1 , an 互素，任意两个整数可能不 互素 （3）同样我们可以定义最小公倍数.整数a,b,c互素且非零，则(ab,c)=(a,c)(b,c)证明：设 (a , c) = d1, (b, c) = d2 . 因为a,b,c互素且非零 ，则(d1, d2 ) = 1, 设 c= d1d2 c, a = d1a, b= d2 b, (ab, c ) = (d1d2ab,c) = d1d2(ab,c) 又因为(ab,c)=1，（如果(ab,c)1 ，则存在整数d满足d| (a,c)或者d|

5、 (b,c) ,这与 (a , c) = d1, (b, c) = d2 矛盾。）所以 (ab,c) = (a,c) (b,c)。7、2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61,67,71,73,79,83,89,97,101,103,107, 109, 113, 127,131,137,139,149,151,157,163,167,173,179,181,191,193,197,199.8、证明： （反证法）假设存在p是素数的平方根是有理数 （不是无理数），即 p是素数的平方根是m/n，其中m,n为 整数且 (m , n)=1。 所以

6、 p = m2/n2 , m2 = n2p . 由于 m|m2, 所以m|p, 即 m = (-)1, 或 m = p(因为p是素数)。（1） m = (-)1，则 1= n2p，矛盾；（2） m = p，则 p= n2 ，与p是素数矛盾。注意：m,n不一定是素数。9、0 n=8k -12k 12; 1 n=8k +1 -12k 12 ; 2 n=8k +2 -12k 12; 3 n=8k +3 -12k 12; 4 n=8k +4 -13k 12; 5 n=8k +5 -13k 11 ; 6 n=8k +6 -13k 11; 7 n=8k +7 -13k 11 10、32=11（mod m）

7、解：m |32-11=21, 所以 m 为21的因子，即 1，3，7，21。 1000=-1 （mod m）解：1001=71113, 所以 m 为，1，7，11，13，77，91，143，1001。 28=1 （mod m）解：255=3517, 所以 m 为1，3，5，17，15，51，85，155。11、m=1,7.12、证明：因为 70 69 62 =(-1) (-2) (-9) (mod 71) =-12 3456789 (mod 71) =1 (mod 71) 所以 70！=61！ (mod 71)13、证明：因为 2 = -1 (mod 3), 所以 2n = (-1)n (mo

8、d 3), 2n +1= (-1)n +1(mod 3).当n为奇数时， 2n +1= 0(mod 3)，即能被3整除.当n为偶数时， 2n +1= 2(mod 3)，即不能被3整除.14、证明: (1) 因为 ac=bc (mod m), 所以存在整数t满足 ac-bc=mt. 因为 (c, m)=d,设 c = d c, m=d m,且(c,m)=1. 所以 ac-bc=(a-b)dc= dmt, 所以 (a-b)c = mt, 所以 ac = bc (mod m) , 又因为 (c, m)=1, 所以 a = b (mod m/d) .证明: (2) 由已知条件得 mi| a-b 1in

9、,则 m1,mn | (a-b)所以 a=b (mod m1,mn ). （11） 对两式进行变形有21=0(mod m), 1001=0(mod m),可以看出要求满足的m即使求21和1001的公约数, 为7和1.（12） (70!)/(61!)= 62*63*70=(-9)*(-8)*(-1)=-9!=-362880=1(mod 71). 明显61!与71互素, 所以两边同乘以61!, 所以70!=61!(mod 71).（13） 当n为奇数时2n=(-1)n=-1=2(mod 3), 两边同时加上1有2n+1=0(mod 3), 所以结论成立. 当n为偶数时2n=(-1)n=1(mod

10、3), 两边同时加上1有2n+1=2(mod 3), 所以结论成立.（14） 第一个问：因为(c,m)=d, m/d为整数.假设ac=k1m+r, bc=k2m+r,有ac=k1d(m/d)+r, bc=k2d(m/d)+r所以ac=bc(mod m/d),因为(c,m/d)=1,所以两边可以同除以一个c, 所以结论成立. 第二个问题：因为a=b(mod m), 所以a-b=ki*mi，a-b是任意mi的倍数，所以a-b是mi公倍数，所以mi|a-b.(利用式子：最小公倍数=每个数的乘积/最大公约数, 是错误的, 该式子在两个数时才成立)（15） 将整数每位数的值相加, 和能被3整除则整数能被

11、3整除, 和能被9整除则整数能被9整除, (1)能被3整除, 不能被9整除，(2)都不能，(3)都不能，(4)都不能15、能被3整除的：（1）能被9整除的：无思考题: 已知(a,b)=1,求(a2+b2,a+b).解：(a2+b2,a+b)= (a2+b2+2ab-2ab, a+b)= (a+b)2-2ab, a+b)= (-2ab, a+b)= (2ab, a+b)当ab=0 (mod 2)时， (2ab, a+b)=1；当ab=1 (mod 2)时， (2ab, a+b)=2。第二章1、 判断方法：分别验证1.对运算是否封闭, 2.对任意的a, b, c是否满足结合律, 3.对任意a是否存

12、在单位元, 4.对任意a是否存在逆元. 可以得出在(1)-(6)中(2),(3),(6)构成群, (1)不满足结合律, (4)不存在单位元, (5)不满足结合律. 不构成群， 无单位元 构成群，单位元是1 构成群，单位元是1/2， 构成群，单位元是1 不构成群，结合律不 成立 构成群，单位元是1 构成群，单位元为单位矩阵 不构成群，单位元为 集合m，除m无逆元 不构成群，单位元为 空集，除空集无逆元 构成群，单位元是1 （789，-2048）= 1 （48385， 97850）= 52、不构成群，结合律不成立4、解：（1）无法判断是否是群，但交换性成立 （2） 是群。5、 证明：显然在群中单位

13、元e满足方程x2=x, 假设存在一个元素a满足方程x2=x, 则有a2=a, 两边同乘以a-1有a=e. 所以在群中只有单位元满足方程x2=x.证明： 在群中，任何元素都有逆元，故 x的逆元x-1，又因为 x2=x，所以 x = x-1 x2= x-1x = e,结论成立。6、 证明：因为群g中每个元素都满足方程x2=e, 所以对群中任意元素a,b有aa=e, bb=e, (ab)2=abab=e. 对abab=e, 方程两边左乘以a, 右乘以b有aababb=(aa)ba(bb)=ba=aeb=ab, 有ab=ba, 所以g是交换群.7、 证明：充分性：因为在群中对任意元素a,b有(ab)2

14、=a2b2即abab=aabb, 方程两边左乘以a的逆元右乘以b的逆元, 有a-1ababb-1= a-1aabbb-1, 有ab=ba, 所以g是交换群. 必要性：因为群g是交换群, 所以对任意元素a,b有ab=ba, 方程两边左乘以a右乘以b有abab=aabb, 有(ab)2=a2b2.证明：设g是交换群，则任何元素 a，b属于 g，ab=ba,所以(ab)2=a(ba)b=a(ab)b=a2b2。 如果任何元素 a，b属于 g，(ab)2=a2b2，则 a-1(ab)2b-1=a-1a2b2b-1，所以 ， ba=ab.8、证明：因为 xaxba = xbc 所以 (xa)-1xaxb

15、a(ba)-1 = (xa)-1 xbc(ba)-1 即 x = a-1 bca-1b-1 所以得到唯一解。 9、 证明：对群中任意元素a,b有ab(ab)-1=e, 方程两边先左乘以a的逆元有b(ab)-1=a-1, 在左乘以b的逆元有(ab)-1=b-1a-1, 所以结论成立.证明：在群中，ab(ab)-1 = e,abb-1a-1 = aea-1 = aa-1 = e, 在群中任何元素的逆元唯一，所以 结论成立。10、证明: (1) 假设a的阶为n，则 an = e, 所以 (a-1)n = e. 如果存在 mn是a-1的阶， 即满足(a-1)m = e, 则 an (a-1)m = e

16、 e = e, 即 an m = e，这与a的阶为n矛盾，所以 a-1 的阶为n.证明: (2) 假设a的阶为n，则 an = e, 所以 (cac-1)n = canc-1 = cec-1 = e. 如果存在 mn是cac-1的阶， 即满足(cac-1)m = e, 则 (cac-1)n (cac-1)m = e e = e, 即 an m = e，这与a的阶为n矛盾， 所以 cac-1 的阶为n.证明: (3) 假设ab的阶为n，则 (ab)n = e, 所以 a-1 (ab)na = a-1 ea = e. 而a-1 (ab)na = (ba)n ,所以 (ba)n = e. 如果存在

17、mn是ba的阶， 即满足(ba)m = e, 则 ban (ba) -m = e e-1 = e, 即 ban m = e，这与ba的阶为m矛盾，所以 ba 的阶为n.证明: (4) 假设abc的阶为n，则 (abc)n = e, 所以 (bca)n = a-1 (abc)na = e. 如果存在 m2. 明显在群中存在一个a-1, 且aa-1(若相等则a2=e, 与a的阶大于2矛盾), 有(a-1)n=e, 所以a-1的阶也大于2. 综上对任意阶大于2的元素a, 存在a-1的阶也大于2. 所以结论成立. 第二个问题：因为在群g中只有e的阶为1, 在由上个结论有阶大于2的元素个数为偶数, 由已

18、知条件g的阶为偶数可知结论成立.5、 对a生成一个阶为n的循环群g, am生成的循环群的阶为n/(n,m)=n. 又因为amg所以am也生成g.6、 设g的阶为n, 由已知可得g为一个群, 有由g与g同态可知f(e)为g的单位元,f(g) g, 且对任意gkg, 有f(gk)=(f(g)k, 所以g中任意元素都可以由f(g)生成表示成(f(g)k, 当k=n时有(f(g)n=f(gn)=f(e), 所以g也是也是一个循环群.8、 13阶：e的阶为1, 其他元素阶为13, 生成元g1到g12. 16阶：e的阶为1, g2阶为8, g4阶为4, g6阶为8, g8阶为2,g10的阶为8, g12的

19、阶为4, g14的阶为8, 其余的g到g15的阶为16且是生成元.9、 先分别求出15阶和20阶的正因子为3,5和2,4,5,10所以15阶的生成元为g3, g5, 20阶的生成元为g2, g4, g5, g10.10、 略 11、 因为p是素数, 所以阶为p的群为循环群(3.3推论3), 又因为任意同阶的有限循环群同构(3.2定理2), 所以结论成立. easy 素数阶群是循环群 构造一一映射 证明保持运算13、 由题意可知am=e, bn=e, m,n为使得上式成立的最小正整数, 又因为ab=ba, 所以(ab)mn=amnbmn=e, 又因为(m,n)=1, 假设存在i使得(ab)i=e

20、,有(ab)mi=e,有bmi=e,有mi|n,有i|n,同理i|m,所以i|mn,所以mn是使得(ab)i=e成立的最小整数，结论成立。证明：因为循环群（a）， （b）的交为e,(如果存在其它元素 c = ai =bj, 则e=(ai )m=bjm ，则 n | jm,又因为(n,m)=1,所以 n | j,即c=e,与假设矛盾） 由于(ab)mn = amnbmn = e，设（ab）k = e, 则ak=b-k,所以ak=b-k = e,所以mn|k所以.15、 设h1, h2是群g的两个正规子群, h= h1h2, 所以有对任意的ag, h1h1有ah1a-1h1, 同样对任意的h2h2

21、有ah2a-1h2, 所以对任意的hh1h2有, aha-1h1h2, 所以结论成立. (先要证明h是g的子群, 略)16、 由题意设eh, ah是h的唯一两个左陪集, 仿照3.4定理2可证. (另证：g=hah, g=hha, 又因为hah=空, hha=空, 所以有ah=ha).证明：设g是群，h是其子群，且指数为2。 所以 g = h ah = h ha, 其中 a 不属于h， 所以ah = ha17、 由题意有hn=nh即对任意的hnhn有hn=nh, 对任意的h1n1hn, h2n2hn, (h1n1)(h2n2)-1= h1n1n2-1h2-1=h1h2-1n1n2hn, 所以结论

22、成立.证明：对任意元素x，y hn, 存在a,c h,b,d n 满足 x = ab, y = cd, 则xy-1=abd-1c-1,由于n是正规子群，则存在c h，b n,满足bd-1c-1 =cb,即xy-1 = acb hn,所以.第四章3、 明显单位元为1, 设c+di是a+bi的逆元, 有(a+bi)(c+di)=1,有c+di=(a-bi)/(a2+b2),所以a+bi的逆元为 (a-bi)/(a2+b2).4、首先证明是加法交换群：对加法封闭,满足加法结合律,有加法单位元,有加法逆元在证明对乘法封闭,乘法结合律,分配律得出是个环.在验证(1,0)为单位元5、 不是环(没有负元)6

23、、 按书上要求分别判断是否满足加法交换群,乘法封闭,乘法结合律,分配律。第一个：是环,没有单位元,是交换环第二个：是环,有单位元1,是交换环第三个：是环,有单位元1,是交换环第四个：不是环(不是加法交换群)11、证明：对任意的x,ys,有ax=0,ay=0,有ax-ay=a(x-y)=0,所以x-ys,又axy=(ax)y=a(xy)=0,所以xys,所以s是r的子环20、证明：设有限整环是s,要证明s是域,需证对全体非零元,都有逆元.设s=a1,a2.an,有1s,对任意非零ai有ais=aia1, aia2. aian,因为乘法封闭有ais=s所以1ais,所以存在aj使得aiai=1,即

24、ai的逆元存在.所以结论成立23、 显然s是一个交换环,单位元为1(具体过程略),且无零因子(设对任意s1=a1+b1i,s2=a2+b2i,假设s1s2=0,若s2不等于0,建立方程a1a2-b1b2=0,a1b2+a2b1=0,变形为a1a2b2=b1b2b2, a1a2b2=-a2a2b1,有因为s2不等于0,可知a2,b2不为0,所以b1=0,推出a1=0,所以s1=0,同理当s1不等于0,s2=0),所以s是一个整环.然而由3题有对于非零元a+bi,逆元为(a-bi)/(a2+b2)不属于s.所以s不是域28、 证明：i是环r的加法子群(具体过程略),对任意的ir,ji,设j=4r, rr, 有ij=ji=4ir, irr, 所以ij=jii,所以i是r的理想. i不等于(4),因为(4)=4x+4n,xr,nz,x取2,n取1有12(4),但是12不属于i,所以不相等.30、 第一个：证明：整数环中既有单位元,