信息安全数学基础课后答案完整版.doc

第一章参考答案

(1)5,4,1,5.

(2)100=22*52,3288=23*3*137.

(4)a,b可以表示成多个素因子的乘积a=pip2—p r? b=q】q2—q、,又因为(a, b)=l, 表明a, b没有公共(相同)素因子.同样可以将a) 9表示为多个素因子相乘a n=(pip2一py, b n=(qiq2一q s)n明显a n, b n也没有公共(相同)素因子.

(5 ) 同样将a, b可以表示成多个素因子的乘积a=pip2一p r, b=qiq2—q s, a n=(PiP2—Pr)L b'-(qiq2—s)L因为a n| b“所以对任意的i有,pi的n次方| b n,所以中必然含有a 的所有素因子，所以b中必然含有a的所有素因子，所以a|b.

(6)因为非零a, b, c 互素，所以(a, b)=(a, c)=l,又因为a=pip2一Pr, b=qiq2—

ab=p)p2—Prqiq?― s,又因为a, b, c互素，所以a, b, c中没有公共(相同)素因孚，明显ab和c也没有公共(相同)素因子.所以(ab, c)= (a, b)(a, 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.

(11)对两式进行变形有21 =0(mod m), 1001=0(mod m),可以看出要求满足的m 即使求21和1001的公约数，为7和1.

(12)(70!)/(61!)= 62*63*—*70=(・9)*(・8)*—*(-l)=・9!=・362880=l(mod 71).明显61!与71互素，所以两边同乘以61!,所以70!=61!(mod71).

(13)当n为奇数时2n=(.l)n=.l=2(mod 3),两边同时加上1有2n+l=0(mod 3), 所以结论成立.

当n为偶数时2n=(-l)n=l(mod 3),两边同时加上1有2n+l=2(mod 3),所以结论成立.

(14 ) 第一个问：因为(c,m)=d, m/d 为整数.假设ac=k]m+r, bc=k2m+r,有ac=k|d(m/d)+r, bc=k2d(m/d)+r 所以ac=bc(mod m/d),因为(c,m/d)=l,所以两边可以同除以一个c,所以结论成立.

第二个问题：因为a=b(mod m),所以a.b=ki*m“ a-b是任意mi的倍数，所以a.b是mi公倍数，所以[mj]|a.b.(利用式子：最小公倍数=每个数的乘积/最大公约数，是错误的，该式子在两个数时才成立)

(15) 将整数每位数的值相加，和能被3整除则整数能被3整除，和能被9整除则整数能被9整除,(1)能被3整除，不能被9整除，(2)都不能，(3)都不能，(4) 都不能

第二章答案

(5)证明：显然在群中单位元c满足方程x2=x,假设存在一•个元素a满足方程x2=x，则有a2=a，两边同乘以广有3『.所以在群中只有单位元满足方程x2=x. (6)证明：因为群G中每个元素都满足方程x2=e,所以对群中任意元素a,b 有aa=e, bb=e, (ab)?=abab=e.对abab=e,方程两边左乘以a,右乘以b有

aababb=(aa)ba(bb)=ba=aeb=ab,有ab=ba,所以G 是交换群.

(7)证明：充分性：因为在群中对任意元素a,b有(ab)2=a2b2即abab=aabb,方程两边左乘以a的逆元右乘以b的逆元，有a-l ababb_,= a_,aabbb-1,有ab=ba,所以G是交换群.

必要性：因为群G是交换群，所以对任意元素a,b有ab-ba,方程两边左乘

以a 右乘以b 有abab=aabb, W(ab)2=a2b2.

(8)证明：因为xaaba=xbc,所以x-1 xaxbaa"1 b-1 =x'1 xbca-1 b-1,所以存在唯一*解

x=a-l bca_,b_|使得方程成立。

(9)证明：对群中任意元素a,b有ab(ab)』=e,方程两边先左乘以a的逆元有

b(ab)」=a』,在左乘以b的逆元有(ab/^b^a \所以结论成立.

(13)证明：设群G的两个子群为G1,G2,则对任意a,beGinG2有ab^GGl, ab-1eG2,所以ab』EGlCG2,所以G1AG2也是G的子群.

(14)证明：设G是一个群，对任意a,beq存在一个G到H的映射f,并且

f(ab)=f(a)f(b).对任意f(a),f(b)eH有f(a)f(b)=f(ab泪H,所以H满足运算的封闭性. 对彳壬意f(a),f(b),f(c) 有(f(a)f(b))f(c)=f(ab)f(c)=f((ab)c),

Ra)(f(b)f(c))=f(a)f(bc)=f(a(bc)),又因为(ab)c=a(bc),所以(f(a)f(b))f(c)=f(a)(f(b)f(c)), 所以H满足结合律.对任意f(a)eH,有f(ac)=f(a)=f(a)f(c),所以f(c)是H的单位元，对任意的f(a)eH,有f(aa-i)=f(e)=f(a)f(a"),所以f(a)的逆元为fR).所以H 是一个群.

(16)证明：设a到a"的------- 映射为f.

充分性:对任意G 中a,b 有f(a)=a-1, f(b)=b \ f(ab)=(ab)-1又因为f 同构，所以f(ab)=f(a)f(b)=(aby1=a-1b-1=(ba)-1,由(ab)1=(ba)-1有ba=ab,所以G 是交换群.

、必要性由上反推可得.

第三章

(2)第一个问题：设该有限群为G,对任意阶大于2的元素aeq有a n=e, n 为使得上式成立的最小正整数且n>2.明显在群中存在一个广，且a尹〜(若相等则a2=e,与a的阶大于2矛盾)，有(广)也，所以a1的阶也大于2.综上对任意阶大于2的元素a,存在a"的阶也大于2.所以结论成立.

第二个问题：因为在群G中只有e的阶为1,在由上个结论有阶大于2 的元素个数为偶数，由已知条件G的阶为偶数可知结论成立.

(5)对a生成一个阶为n的循环群G, a'"生成的循环群的阶为n/(n,m)=n.又因为am^G所以a*11也生成G.

(6)设G的阶为n,由己知可得G'为一个群，有由G与G'同态可知f(c)为G'的单位元,f(g) EG',且对任意g k eq有f(g k)=(f(g))\所以G'中任意元素都可以由f(g)生成表示成(职)火当k=n时•有(f(g))n=f(gn)=f(e),所以G'也是也是一•个循环群. (8)13阶：e的阶为1,其他元素阶为13,生成元g1到g12.

16阶:c的阶为1, g2阶为8, g4阶为4, g6阶为8, g'阶为2,g10的阶为8, g12 的阶为4, g14的阶为8,其余的g到g15的阶为16且是生成元.

(9)先分别求出15阶和20阶的正因子为3,5和245,10所以15阶的生成元为

g3,g5,20阶的生成元为g"，, g5,g10.

(10)略

(11)因为p是素数，所以阶为p的群为循环群(3.3推论3),又因为任意同阶的有限循环群同构(3.2定理2),所以结论成立.

(12)因为p是P111的因子，p是一个素数，由有限群G的子群H中，H阶是G

阶因子可知，P01阶群一定有阶为P的子群。