信息安全數(shù)學(xué)基礎(chǔ)答案第一二三四五章(許春香 廖永建)

1、第一章1、 5,4,1,5.2、 100=22*52, 3288=23*3*137.4、 a,b可以表示成多個(gè)素因子的乘積a=p1p2pr, b=q1q2qs,又因?yàn)?a, b)=1，表明a, b沒有公共(相同)素因子. 同樣可以將an, bn表示為多個(gè)素因子相乘an=(p1p2pr)n, bn=(q1q2qs)n明顯an, bn也沒有公共(相同)素因子.證明：由于（a,b）=1，由互素性質(zhì)3（如果（a,c）=1 （b,c）=1,則 （ab,c）=1）得 （a2,b）=1，因此得 （an, b）=1 ，同理得 （an, bn）=1.5、 同樣將a, b可以表示成多個(gè)素因子的乘積a=p1p2pr

2、, b=q1q2qs, an=(p1p2pr)n, bn=(q1q2qs)n,因?yàn)閍n| bn所以對(duì)任意的i有, pi的n次方| bn, 所以bn中必然含有a的所有素因子, 所以b中必然含有a的所有素因子, 所以a|b.證明：設(shè)a=q1q2qr, b=p1p2ps, 其中qi, pj 為素?cái)?shù)。 因?yàn)閍nbn，所以abnq1q2qr p1np2nps n又由定理1（page7），存在j1滿足 q1 pj1n又因?yàn)閜j 為素?cái)?shù)，所以有 q1 = pj1同理得q2 = pj2 , qr = pjr,得 a= q1q2qr =pj1 pj2 pjr p1p2ps = b .注意：在證明過程沒使用標(biāo)準(zhǔn)因

3、子分解式！6、 因?yàn)榉橇鉧, b, c互素,所以(a, b)=(a, c)=1,又因?yàn)閍=p1p2pr, b=q1q2qs, ab=p1p2prq1q2qs, 又因?yàn)閍, b, c互素, 所以a, b, c中沒有公共(相同)素因子, 明顯ab和c也沒有公共(相同)素因子.所以(ab, c)= (a, b)(a, c).定義：（1）如果整數(shù)dai (1 i n) ,則d稱為ai的公因子（2）設(shè)d0是ai (1 i n)的公因子，如果ai (1 i n) 的任何公因子都整除d，則d稱為ai (1 i n)的最大公因子，記為d= (a1,an)（3）如果d = 1, 則稱整數(shù)a1 , an 互素。注

4、意：（1）整數(shù)a , b 互素的充要條件存在整數(shù) s,t 滿足 sa+tb=1. s, t是否唯一？（2）整數(shù)a1 , an 互素，任意兩個(gè)整數(shù)可能不 互素 （3）同樣我們可以定義最小公倍數(shù).整數(shù)a,b,c互素且非零，則(ab,c)=(a,c)(b,c)證明：設(shè) (a , c) = d1, (b, c) = d2 . 因?yàn)閍,b,c互素且非零 ，則(d1, d2 ) = 1, 設(shè) c= d1d2 c, a = d1a, b= d2 b, (ab, c ) = (d1d2ab,c) = d1d2(ab,c) 又因?yàn)?ab,c)=1，（如果(ab,c)1 ，則存在整數(shù)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、證明： （反證法）假設(shè)存在p是素?cái)?shù)的平方根是有理數(shù) （不是無理數(shù)），即 p是素?cái)?shù)的平方根是m/n，其中m,n為 整數(shù)且 (m , n)=1。 所以

6、 p = m2/n2 , m2 = n2p . 由于 m|m2, 所以m|p, 即 m = (-)1, 或 m = p(因?yàn)閜是素?cái)?shù))。（1） m = (-)1，則 1= n2p，矛盾；（2） m = p，則 p= n2 ，與p是素?cái)?shù)矛盾。注意：m,n不一定是素?cái)?shù)。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、證明：因?yàn)?70 69 62 =(-1) (-2) (-9) (mod 71) =-12 3456789 (mod 71) =1 (mod 71) 所以 70！=61！ (mod 71)13、證明：因?yàn)?2 = -1 (mod 3), 所以 2n = (-1)n (mo

8、d 3), 2n +1= (-1)n +1(mod 3).當(dāng)n為奇數(shù)時(shí)， 2n +1= 0(mod 3)，即能被3整除.當(dāng)n為偶數(shù)時(shí)， 2n +1= 2(mod 3)，即不能被3整除.14、證明: (1) 因?yàn)?ac=bc (mod m), 所以存在整數(shù)t滿足 ac-bc=mt. 因?yàn)?(c, m)=d,設(shè) c = d c, m=d m,且(c,m)=1. 所以 ac-bc=(a-b)dc= dmt, 所以 (a-b)c = mt, 所以 ac = bc (mod m) , 又因?yàn)?(c, m)=1, 所以 a = b (mod m/d) .證明: (2) 由已知條件得 mi| a-b 1in

9、,則 m1,mn | (a-b)所以 a=b (mod m1,mn ). （11） 對(duì)兩式進(jìn)行變形有21=0(mod m), 1001=0(mod m),可以看出要求滿足的m即使求21和1001的公約數(shù), 為7和1.（12） (70!)/(61!)= 62*63*70=(-9)*(-8)*(-1)=-9!=-362880=1(mod 71). 明顯61!與71互素, 所以兩邊同乘以61!, 所以70!=61!(mod 71).（13） 當(dāng)n為奇數(shù)時(shí)2n=(-1)n=-1=2(mod 3), 兩邊同時(shí)加上1有2n+1=0(mod 3), 所以結(jié)論成立. 當(dāng)n為偶數(shù)時(shí)2n=(-1)n=1(mod

10、3), 兩邊同時(shí)加上1有2n+1=2(mod 3), 所以結(jié)論成立.（14） 第一個(gè)問：因?yàn)?c,m)=d, m/d為整數(shù).假設(shè)ac=k1m+r, bc=k2m+r,有ac=k1d(m/d)+r, bc=k2d(m/d)+r所以ac=bc(mod m/d),因?yàn)?c,m/d)=1,所以兩邊可以同除以一個(gè)c, 所以結(jié)論成立. 第二個(gè)問題：因?yàn)閍=b(mod m), 所以a-b=ki*mi，a-b是任意mi的倍數(shù)，所以a-b是mi公倍數(shù)，所以mi|a-b.(利用式子：最小公倍數(shù)=每個(gè)數(shù)的乘積/最大公約數(shù), 是錯(cuò)誤的, 該式子在兩個(gè)數(shù)時(shí)才成立)（15） 將整數(shù)每位數(shù)的值相加, 和能被3整除則整數(shù)能被

11、3整除, 和能被9整除則整數(shù)能被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)當(dāng)ab=0 (mod 2)時(shí)， (2ab, a+b)=1；當(dāng)ab=1 (mod 2)時(shí)， (2ab, a+b)=2。第二章1、 判斷方法：分別驗(yàn)證1.對(duì)運(yùn)算是否封閉, 2.對(duì)任意的a, b, c是否滿足結(jié)合律, 3.對(duì)任意a是否存

12、在單位元, 4.對(duì)任意a是否存在逆元. 可以得出在(1)-(6)中(2),(3),(6)構(gòu)成群, (1)不滿足結(jié)合律, (4)不存在單位元, (5)不滿足結(jié)合律. 不構(gòu)成群， 無單位元 構(gòu)成群，單位元是1 構(gòu)成群，單位元是1/2， 構(gòu)成群，單位元是1 不構(gòu)成群，結(jié)合律不 成立 構(gòu)成群，單位元是1 構(gòu)成群，單位元為單位矩陣 不構(gòu)成群，單位元為 集合m，除m無逆元 不構(gòu)成群，單位元為 空集，除空集無逆元 構(gòu)成群，單位元是1 （789，-2048）= 1 （48385， 97850）= 52、不構(gòu)成群，結(jié)合律不成立4、解：（1）無法判斷是否是群，但交換性成立 （2） 是群。5、 證明：顯然在群中單位

13、元e滿足方程x2=x, 假設(shè)存在一個(gè)元素a滿足方程x2=x, 則有a2=a, 兩邊同乘以a-1有a=e. 所以在群中只有單位元滿足方程x2=x.證明： 在群中，任何元素都有逆元，故 x的逆元x-1，又因?yàn)?x2=x，所以 x = x-1 x2= x-1x = e,結(jié)論成立。6、 證明：因?yàn)槿篻中每個(gè)元素都滿足方程x2=e, 所以對(duì)群中任意元素a,b有aa=e, bb=e, (ab)2=abab=e. 對(duì)abab=e, 方程兩邊左乘以a, 右乘以b有aababb=(aa)ba(bb)=ba=aeb=ab, 有ab=ba, 所以g是交換群.7、 證明：充分性：因?yàn)樵谌褐袑?duì)任意元素a,b有(ab)2

14、=a2b2即abab=aabb, 方程兩邊左乘以a的逆元右乘以b的逆元, 有a-1ababb-1= a-1aabbb-1, 有ab=ba, 所以g是交換群. 必要性：因?yàn)槿篻是交換群, 所以對(duì)任意元素a,b有ab=ba, 方程兩邊左乘以a右乘以b有abab=aabb, 有(ab)2=a2b2.證明：設(shè)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、證明：因?yàn)?xaxba = xbc 所以 (xa)-1xaxb

15、a(ba)-1 = (xa)-1 xbc(ba)-1 即 x = a-1 bca-1b-1 所以得到唯一解。 9、 證明：對(duì)群中任意元素a,b有ab(ab)-1=e, 方程兩邊先左乘以a的逆元有b(ab)-1=a-1, 在左乘以b的逆元有(ab)-1=b-1a-1, 所以結(jié)論成立.證明：在群中，ab(ab)-1 = e,abb-1a-1 = aea-1 = aa-1 = e, 在群中任何元素的逆元唯一，所以 結(jié)論成立。10、證明: (1) 假設(shè)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) 假設(shè)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) 假設(shè)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) 假設(shè)abc的階為n，則 (abc)n = e, 所以 (bca)n = a-1 (abc)na = e. 如果存在 m2. 明顯在群中存在一個(gè)a-1, 且aa-1(若相等則a2=e, 與a的階大于2矛盾), 有(a-1)n=e, 所以a-1的階也大于2. 綜上對(duì)任意階大于2的元素a, 存在a-1的階也大于2. 所以結(jié)論成立. 第二個(gè)問題：因?yàn)樵谌篻中只有e的階為1, 在由上個(gè)結(jié)論有階大于2的元素個(gè)數(shù)為偶數(shù), 由已

18、知條件g的階為偶數(shù)可知結(jié)論成立.5、 對(duì)a生成一個(gè)階為n的循環(huán)群g, am生成的循環(huán)群的階為n/(n,m)=n. 又因?yàn)閍mg所以am也生成g.6、 設(shè)g的階為n, 由已知可得g為一個(gè)群, 有由g與g同態(tài)可知f(e)為g的單位元,f(g) g, 且對(duì)任意gkg, 有f(gk)=(f(g)k, 所以g中任意元素都可以由f(g)生成表示成(f(g)k, 當(dāng)k=n時(shí)有(f(g)n=f(gn)=f(e), 所以g也是也是一個(gè)循環(huán)群.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、 因?yàn)閜是素?cái)?shù), 所以階為p的群為循環(huán)群(3.3推論3), 又因?yàn)槿我馔A的有限循環(huán)群同構(gòu)(3.2定理2), 所以結(jié)論成立. easy 素?cái)?shù)階群是循環(huán)群 構(gòu)造一一映射 證明保持運(yùn)算13、 由題意可知am=e, bn=e, m,n為使得上式成立的最小正整數(shù), 又因?yàn)閍b=ba, 所以(ab)mn=amnbmn=e, 又因?yàn)?m,n)=1, 假設(shè)存在i使得(ab)i=e

20、,有(ab)mi=e,有bmi=e,有mi|n,有i|n,同理i|m,所以i|mn,所以mn是使得(ab)i=e成立的最小整數(shù)，結(jié)論成立。證明：因?yàn)檠h(huán)群（a）， （b）的交為e,(如果存在其它元素 c = ai =bj, 則e=(ai )m=bjm ，則 n | jm,又因?yàn)?n,m)=1,所以 n | j,即c=e,與假設(shè)矛盾） 由于(ab)mn = amnbmn = e，設(shè)（ab）k = e, 則ak=b-k,所以ak=b-k = e,所以mn|k所以.15、 設(shè)h1, h2是群g的兩個(gè)正規(guī)子群, h= h1h2, 所以有對(duì)任意的ag, h1h1有ah1a-1h1, 同樣對(duì)任意的h2h2

21、有ah2a-1h2, 所以對(duì)任意的hh1h2有, aha-1h1h2, 所以結(jié)論成立. (先要證明h是g的子群, 略)16、 由題意設(shè)eh, ah是h的唯一兩個(gè)左陪集, 仿照3.4定理2可證. (另證：g=hah, g=hha, 又因?yàn)閔ah=空, hha=空, 所以有ah=ha).證明：設(shè)g是群，h是其子群，且指數(shù)為2。 所以 g = h ah = h ha, 其中 a 不屬于h， 所以ah = ha17、 由題意有hn=nh即對(duì)任意的hnhn有hn=nh, 對(duì)任意的h1n1hn, h2n2hn, (h1n1)(h2n2)-1= h1n1n2-1h2-1=h1h2-1n1n2hn, 所以結(jié)論

22、成立.證明：對(duì)任意元素x，y hn, 存在a,c h,b,d n 滿足 x = ab, y = cd, 則xy-1=abd-1c-1,由于n是正規(guī)子群，則存在c h，b n,滿足bd-1c-1 =cb,即xy-1 = acb hn,所以.第四章3、 明顯單位元為1, 設(shè)c+di是a+bi的逆元, 有(a+bi)(c+di)=1,有c+di=(a-bi)/(a2+b2),所以a+bi的逆元為 (a-bi)/(a2+b2).4、首先證明是加法交換群：對(duì)加法封閉,滿足加法結(jié)合律,有加法單位元,有加法逆元在證明對(duì)乘法封閉,乘法結(jié)合律,分配律得出是個(gè)環(huán).在驗(yàn)證(1,0)為單位元5、 不是環(huán)(沒有負(fù)元)6

23、、 按書上要求分別判斷是否滿足加法交換群,乘法封閉,乘法結(jié)合律,分配律。第一個(gè)：是環(huán),沒有單位元,是交換環(huán)第二個(gè)：是環(huán),有單位元1,是交換環(huán)第三個(gè)：是環(huán),有單位元1,是交換環(huán)第四個(gè)：不是環(huán)(不是加法交換群)11、證明：對(duì)任意的x,ys,有ax=0,ay=0,有ax-ay=a(x-y)=0,所以x-ys,又axy=(ax)y=a(xy)=0,所以xys,所以s是r的子環(huán)20、證明：設(shè)有限整環(huán)是s,要證明s是域,需證對(duì)全體非零元,都有逆元.設(shè)s=a1,a2.an,有1s,對(duì)任意非零ai有ais=aia1, aia2. aian,因?yàn)槌朔ǚ忾]有ais=s所以1ais,所以存在aj使得aiai=1,即

24、ai的逆元存在.所以結(jié)論成立23、 顯然s是一個(gè)交換環(huán),單位元為1(具體過程略),且無零因子(設(shè)對(duì)任意s1=a1+b1i,s2=a2+b2i,假設(shè)s1s2=0,若s2不等于0,建立方程a1a2-b1b2=0,a1b2+a2b1=0,變形為a1a2b2=b1b2b2, a1a2b2=-a2a2b1,有因?yàn)閟2不等于0,可知a2,b2不為0,所以b1=0,推出a1=0,所以s1=0,同理當(dāng)s1不等于0,s2=0),所以s是一個(gè)整環(huán).然而由3題有對(duì)于非零元a+bi,逆元為(a-bi)/(a2+b2)不屬于s.所以s不是域28、 證明：i是環(huán)r的加法子群(具體過程略),對(duì)任意的ir,ji,設(shè)j=4r, rr, 有ij=ji=4ir, irr, 所以ij=jii,所以i是r的理想. i不等于(4),因?yàn)?4)=4x+4n,xr,nz,x取2,n取1有12(4),但是12不屬于i,所以不相等.30、 第一個(gè)：證明：整數(shù)環(huán)中既有單位元,