信息安全數(shù)學(xué)基礎(chǔ)習(xí)題答案

信息安全數(shù)學(xué)基礎(chǔ)習(xí)題答案第一章整數(shù)的可除性1．證明：因?yàn)?|n所以n=2k,kZ5|n所以5|2k，又（5，2）=1，所以5|k即k=5k1，k1Z7|n所以7|2*5k1,又（7，10）=1，所以7|k1即k1=7k2，k2Z所以n=2*5*7k2即n=70k2,k2因此70|nZ2．證明：因?yàn)閍3-a=(a-1)a(a+1)當(dāng)a=3k，kZ3|a則3|a3-a當(dāng)a=3k-1，kZ3|a+1則3|a3-a當(dāng)a=3k+1，kZ3|a-1則3|a3-a所以a3-a能被3整除。3．證明：任意奇整數(shù)可表示為2k0+1，k0（2k0+1）2＝4k02+4k0+1=4k0(k0+1)+1Z由于k0與k0+1為兩連續(xù)整數(shù)，必有一個(gè)為偶數(shù)，所以k0(k0+1)=2k所以（2k0+1）2=8k+1得證。4．證明：設(shè)三個(gè)連續(xù)整數(shù)為a-1,a,a+1則(a-1)a(a+1)=a3-a由第二題結(jié)論3|（a3-a）即3|(a-1)a(a+1)又三個(gè)連續(xù)整數(shù)中必有至少一個(gè)為偶數(shù)，則2|(a-1)a(a+1)又（3，2）=1所以6|(a-1)a(a+1)得證。5．證明：構(gòu)造下列k個(gè)連續(xù)正整數(shù)列：(k+1)！+2,(k+1)！+3,(k+1)！+4,……,(k+1)！+(k+1),kZ對(duì)數(shù)列中任一數(shù)(k+1)！+i=i[(k+1)k…(i+1)(i-1)…2*1+1],i=2,3,4,…(k+1)所以i|(k+1)！+i即(k+1)！+i為合數(shù)所以此k個(gè)連續(xù)正整數(shù)都是合數(shù)。6．證明：因?yàn)?911/2＜14,小于14的素?cái)?shù)有2，3，5，7，11，13經(jīng)驗(yàn)算都不能整除191所以191為素?cái)?shù)。因?yàn)?471/2＜24,小于24的素?cái)?shù)有2，3，5，7，11，13，17，19，23經(jīng)驗(yàn)算都不能整除547所以547為素?cái)?shù)。由737=11*67,747=3*249知737與747都為合數(shù)。8．解：存在。eg：a=6,b=2,c=910．證明：p1p2p3|n，則n=p1p2p3k，kN+又p1≤p2≤p3，所以n=p1p2p3k≥p13即p13≤n1/3p1為素?cái)?shù)則p1≥2，又p1≤p2≤p3，所以n=p1p2p3k≥2p2p3≥2p22即p2≤(n/2)1/2得證。11．解：小于等于5001/2的所有素?cái)?shù)為2，3，5，7，11，13，17，19，依次刪除這些素?cái)?shù)的倍數(shù)可得所求素?cái)?shù)：12．證明：反證法假設(shè)3k+1沒有相同形式的素因數(shù)，則它一定只能表示成若干形如3k-1的素?cái)?shù)相乘。(3k1+1)(3k2+1)=[(3k1+1)k2+k1]*3+1顯然若干個(gè)3k+1的素?cái)?shù)相乘，得到的還是3k+1的形式，不能得出3k-1的數(shù)，因此假設(shè)不成立，結(jié)論得證。同理可證其他。13．證明：反證法假設(shè)形如4k+3的素?cái)?shù)只有有限個(gè)，記為p1,p2,…,pn因?yàn)?k+3=4k`-1=4k-1構(gòu)造N=4*p1*p2*…*pn-1≥3*p1*p2*…*pn所以N＞pi(i=1,2,…,n)N為4k-1形式的素?cái)?shù)，即為4k+3的形式，所以假設(shè)不成立。原結(jié)論正確，形如4k+3的素?cái)?shù)有無(wú)窮多個(gè)。28．（1）解：85=1*55+3055=1*30+2530=1*25+525=5*5所以(55,85)=5（2）解：282=1*202+80202=2*80+4280=1*42+3842=1*38+438=9*4+24=2*2所以（202,282）=229．（1）解：2t+1=1*(2t-1)+22t-1=(t-1)*2+12=2*1所以（2t+1,2t-1）=1（2）解：2(n+1)=1*2n+22n=n*2所以（2n,2(n+1)）=232．（1）解：1=3-1*2=3-1*(38-12*3)=-38+13*(41-1*38)=13*41-14*(161-3*41)=-14*161+55*(363-2*161)=55*363+(-124)*(1613-4*363)=(-124)*1613+551*(3589-2*1613)=551*3589+(-1226)*1613所以s=-1226t=551（2）解：1=4-1*3=4-1*(115-28*4)=-115+29*(119-1*115)=29*119+(-30)*(353-2*119)=-30*353+89*(472-1*353)=89*472+(-119)*(825-1*472)=(-119)*825+208*(2947-3*825)=208*2947+(-743)*(3772-1*2947)=951*2947+(-743)*3772所以s=951t=-74336．證明：因?yàn)椋╝，4）=2所以a=2*(2m+1)mZ所以a+b=4m+2+4n+2=4(m+n)+4=4(m+n+1)即4|a+b所以（a+b,4）=437．證明：反證法假設(shè)n為素?cái)?shù)，則n|a2-b2=(a+b)(a-b)由1.4定理2知n|a+b或n|a-b,與已知條件矛盾所以假設(shè)不成立，原結(jié)論正確，n為合數(shù)。40．證明：（1）假設(shè)是21/2有理數(shù)，則存在正整數(shù)p，q，使得21/2=p/q,且（p,q）=1平方得：p2=2q2,即2|p2，所以p=2m,mN因此p2=4m2=2q2q2=2m2則（p,q）=(2m,2n)=2(m,n)≥2與（p,q）=1矛盾所以假設(shè)不成立，原結(jié)論正確，21/2q=2n,nN不是有理數(shù)。（2）假設(shè)是71/2有理數(shù)，則存在正整數(shù)m，n，使得71/2=p/q,且（m,n）=1平方得：m2=2n2,即7|m2將m表示成n個(gè)素?cái)?shù)pi的乘積，m=p1p2p3……pn，pi為素?cái)?shù)。因?yàn)?為素?cái)?shù)，假設(shè)7!|m，則7!∈｛p1，p2，p3，……pn｝所以m2=p12p22p32……pn2=(p1p2p3……pn)(p1p2p3……pn)所以7!|m2，與7|m2矛盾，故7|m,m=7k同理可知：7|n,n=7k0所以(m,n)=(7k,7k0)=7(k,k0)≥7與已知矛盾故原結(jié)論正確，71/2不是有理數(shù)。不是有理數(shù)。（3）同理可證171/241．證明：假設(shè)log210是有理數(shù)，則存在正整數(shù)p,q,使得log210=p/q,且（p,q）=1又log210=ln10/ln2=p/qLn10q=ln2p10q=2p(2*5)q=2p5q=2p-q所以只有當(dāng)q=p=0是成立，所以假設(shè)不成立故原結(jié)論正確，log210是無(wú)理數(shù)。同理可證log37，log1521都是無(wú)理數(shù)。50．（1）解：因?yàn)?=23,60=22*3*5所以[8,60]=23*3*5=12051．（4）解：(471179111011001,4111831111011000)=4104707908301011000=1011000[471179111011001,4111831111011000]=4111471179111831111011001第二章．同余1．解：（1）其中之一為9，19，11，21，13，23，15，25，17（2）其中之一為0，10，20，30，40，50，60，70，80（3）.（1）或（2）中的要求對(duì)模10不能實(shí)現(xiàn)。2．證明：當(dāng)m>2時(shí)，因?yàn)?m-1)2=m2-2m+1=m(m-2)+1所以(m-1)2≡1(modm)即1與(m-1)2在同一個(gè)剩余類中，故02,12,…,(m-1)2一定不是模m的完全剩余系。6．解：21≡2(mod7),22≡4(mod7),23≡1(mod7)又20080509=6693503*3所以220080509=(23)6693503≡1(mod7)故220080509是星期六。7．證明：（i）因?yàn)閍i≡bi(modm),1≤i≤k又a1+a2+…+ak=∑ai=∑(bi+kim)=∑bi+m*∑ki所以有∑ai≡∑bi(modm)所以ai=bi+kim即a1+a2+…+ak=b1+b2+…+bk(modm)（ii）因?yàn)閍i≡bi(modm),1≤i≤k所以ai(modm)=bi(modm)所以（a1a2…ak）modm≡[(a1modm)(a2modm)…(akmodm)]modm≡[(b1modm)(b2modm)…(bkmodm)]modm≡（b1b2…bk）modm所以a1a2…ak≡a1a2…ak(modm)8．證明：如果a2≡b2(modp)則a2=b2+kp,kZ即kp=a2-b2=(a+b)(a-b)所以p|(a+b)(a-b)又p為素?cái)?shù)，根據(jù)1.4定理2知p|a+b或p|a-b得證。9．證明：如果a2≡b2(modn)則a2=b2+kn,kZ即kn=a2-b2=(a+b)(a-b)所以n|(a+b)(a-b)由n=pq知kpq=a2-b2=(a+b)(a-b)因?yàn)閚!|a-b,n!|a+b，所以p,q不能同時(shí)為a-b或a+b的素因數(shù)。不妨設(shè)p|a-b,q|a+b,則q!|a-b,p!|a+b即(q,a-b)=1,(p,a+b)=1因此(n,a-b)=(pq,a-b)=(p,a-b)=p>1(n,a+b)=(pq,a+b)=(q,a+b)=q>1故原命題成立。10．證明：因?yàn)閍≡b(modc)則a=cq+b,qZ根據(jù)1.3定理3知(a,c)=(b,c)17．解：（1）ak+ak-1+…+a=1+8+4+3+5+8+1=30因?yàn)?|30,9!|30所以1843581能被3整除，不能被9整除。（2）ak+ak-1+…+a=1+8+4+2+3+4+0+8+1=31因?yàn)?!|31,9!|31所以184234081不能被3整除，也不能被9整除。00（3）ak+ak-1+…+a=8+9+3+7+7+5+2+7+4+4=56因?yàn)?!|56,9!|56所以8937752744不能被3整除，也不能被9整除。（4）ak+ak-1+…+a=4+1+5+3+7+6+8+9+1+2+2+4+6=5800因?yàn)?!|58,9!|58所以4153768912246不能被3整除，也不能被9整除。20．解：（89878*58965）mod9≡[(89878mod9)*(58965mod9)]mod9≡(4*6)mod9≡6(mod9)≡5299?56270(mod9)又5299?56270≡(45+?)mod9≡?(mod9)所以?=6即未知數(shù)字為6。21．解：（1）因?yàn)?75961*2753≡[(36mod9)(17mod9)]mod9≡0(mod9)2410520633≡26(mod9)≡8(mod9)所以等式875961*2753=2410520633不成立（2）因?yàn)?4789*23567≡[(29mod9)(23mod9)]mod9≡1(mod9)348532367≡41(mod9)≡5(mod9)所以等式14789*23567=348532367不成立（3）因?yàn)?4789*43717≡[(30mod9)(22mod9)]mod9≡3(mod9)1092700713≡30(mod9)≡3(mod9)所以等式24789*43717=1092700713可能成立（4）這種判斷對(duì)于判斷等式不成立時(shí)簡(jiǎn)單明了，但對(duì)于判斷等式成立時(shí)，可能會(huì)較復(fù)雜。22．解：因?yàn)?為素?cái)?shù)，由Wilso定理知：(7-1)!≡-1(mod7)即6！≡-1（mod7）所以8*9*10*11*12*13≡1*2*3*4*5*6(mod7)≡6!(mod7)≡-1(mod7)31．證明：因?yàn)閏1,c2,…,c(m)是模m的簡(jiǎn)化剩余系對(duì)于任一ci，有m-ci也屬于模m的簡(jiǎn)化剩余系所以ci+(m-ci)≡0(modm)因此c1+c2+…+c(m)≡0(modm)32．證明：因?yàn)閍(m)≡1(modm)所以a(m)-1≡0(modm)a(m)-1=(a-1)(1+a+a2+…+a(m)-1)≡0(modm)又（a-1,m）=1所以1+a+a2+…+a(m)-1≡0(modm)33．證明：因?yàn)?為素?cái)?shù)，由Fermat定理知a7≡a(mod7)又（a，3）=1所以(a,9)=1由Euler定理知a(9)≡a6≡1(mod9)即a7≡a(mod9)又(7,9)=1,所以a7≡a(mod7*9)即a7≡a(mod63)34．證明：因?yàn)?2760=23*32*5*7*13又(a,32760)=1所以(a,2)=(a,3)=(a,5)=(a,7)=(a,13)=1有：a(13)≡1(mod13)即a12≡1(mod13)aaaa(8)≡a4≡1(mod8)即a12≡1(mod8)(5)≡a4≡1(mod5)即a12≡1(mod5)(7)≡a6≡1(mod7)即a12≡1(mod7)(9)≡a6≡1(mod9)即a12≡1(mod9)又因?yàn)閇5,7,8,9,13]=32760所以a12≡1(mod32760)35．證明：因?yàn)?p,q)=1p,q都為素?cái)?shù)所以(p)=p-1,(q)=q-1由Euler定理知：p(q)≡1(modq)q(p)≡1(modp)即pq-1≡1(modq)qp-1又qp-1≡0(modq)pq-1所以pq-1+qp-1≡1(modq)qp-1+pq-1≡1(modp)≡0(modp)≡1(modp)又[p,q]=pq所以pq-1+qp-136．證明：因?yàn)?m,n)=1≡1(modpq)由Euler定理知：m(n)≡1(modn)n(m)≡1(modm)所以m(n)+n(m)≡(m(n)modn)+(n(m)modn)≡1+0≡1(modn)同理有：m(n)+n(m)≡1(modm)又[m,n]=mn所以m(n)+n(m)≡1(modmn)第三章.同余式1．（1）解：因?yàn)椋?，7）=1|2故原同余式有解又3x≡1（mod7）所以特解x0`≡5（mod7）同余式3x≡2（mod7）的一個(gè)特解x0≡2*x0`=2*5≡3（mod7）所有解為：x≡3（mod7）（3）解：因?yàn)椋?7，21）=1|14故原同余式有解又17x≡1（mod21）所以特解x0`≡5（mod21）同余式17x≡14（mod21）的一個(gè)特解x0≡14*x0`=14*5≡7（mod21）所有解為：x≡7（mod21）2．（1）解：因?yàn)椋?27，1012）=1|833故原同余式有解又127x≡1（mod1012）所以特解x0`≡255（mod1012）同余式127x≡833（mod1012）的一個(gè)特解x0≡833*x0`=833*255≡907（mod1012）所有解為：x≡907（mod1012）3．見課本3.2例17．（1）解：因?yàn)椋?，14）=1由Euler定理知，同余方程5x≡3（mod14）的解為：x≡5(14)-1*3≡9（mod14）（2）解：因?yàn)椋?，15）=1由Euler定理知，同余方程4x≡7（mod15）的解為：x≡4(15)-1*7≡13（mod15）（3）解：因?yàn)椋?，16）=1由Euler定理知，同余方程3x≡5（mod16）的解為：x≡3(16)-1*5≡7（mod16）11．證明：由中國(guó)剩余定理知方程解為：x≡a1M1M1`+a2M2M2`+……+akMkMk`（modm）因?yàn)閙i兩兩互素，又中國(guó)剩余定理知：MiMi`≡1（modmi）又Mi=m/mi所以（m，Mi）≡1（modmi）所以MiMi`=Mi(mi)≡（modmi）代入方程解為x≡a1M1(m1)+a2M2(m2)+……+akMk(mk)(modm)得證。12．（1）解：由方程組得：3x+3y≡2(mod7)6x+6y≡4(mod7)x+y≡-4(mod7)X≡5(mod7)y≡5(mod7)（2）解：由方程組得：2x+6y≡2(mod7)2x-y≡2(mod7)6x+8y≡4(mod7)x-y≡-4(mod7)X≡6(mod7)y≡3(mod7)13．見課本3.2例414．同課本3.2例321000000≡562（mod1309）15．（1）解：等價(jià)同余式組為：23x≡1（mod4）23x≡1（mod5）23x≡1（mod7）所以x≡3（mod4）x≡2（mod5）所以x≡3*35*3+2*28*2+4*20*6≡67（mod140）（2）解：等價(jià)同余式組為：17x≡1（mod4）x≡4（mod7）17x≡1（mod5）17x≡1（mod7）17x≡1（mod11）所以x≡1（mod4）x≡2（mod5）x≡-3（mod7）x≡7（mod11）所以x≡1*385*1+2*308*2+(-3)*220*5+7*140*7≡557（mod1540）19．解：3x14+4x13+2x11+x9+x6+x3+12x2+x≡0（mod7）左邊=(x7-x)(3x7+4x6+2x4+x2+3x+4)+x6+2x5+2x2+15x2+5x所以原同余式可化簡(jiǎn)為：x6+2x5+2x2+15x2+5x≡0（mod7）直接驗(yàn)算得解為：x≡0（mod7）x≡6（mod7）20．解：f`(x)≡4x3+7（mod243）直接驗(yàn)算的同余式f（x）≡0(mod3)有一解：x1≡1（mod3）f`(x1)≡4*13*7=-1(mod3)f`(x1)-1≡-1(mod3)所以t1≡-f（x1）*(f`(x1)-1(mod3))/31≡1(mod3)x2≡x1+3t1≡4(mod9)t2≡-f（x2）*(f`(x1)-1(mod3))/32≡2(mod3)x3≡x2+32t2≡22(mod27)t3≡-f（x3）*(f`(x1)-1(mod3))/33≡0(mod3)x4≡x3+33t3≡22(mod81)t5≡-f（x4）*(f`(x1)-1(mod3))/34≡2(mod3)x5≡x4+34t4≡184(mod243)所以同余式f（x）≡0(mod243)的解為：x5≡184(mod243)第四章．二次同余式與平方剩余2．解：對(duì)x=0,1,2,3,4,5,6時(shí)，分別求出yx=0,y2≡1(mod7),y≡1,6(mod7)x=4,y2≡4(mod7),y≡2,5(mod7)當(dāng)x=1,2,3,5,6時(shí)均無(wú)解5．解：對(duì)x=0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16時(shí)，分別求出yx=0,y2≡1(mod17),y≡1,16(mod17)x=1,y2≡3(mod17),無(wú)解x=2,y2≡11(mod17),無(wú)解x=3,y2≡14(mod17),無(wú)解x=4,y2≡1(mod17),y≡1,16(mod17)x=5,y2≡12(mod17),無(wú)解x=6,y2≡2(mod17),y≡6,11(mod17)x=7,y2≡11(mod17),無(wú)解x=8,y2≡11(mod17),無(wú)解x=9,y2≡8(mod17),y≡5,12(mod17)x=10,y2≡8(mod17),y≡5,12(mod17)x=11,y2≡0(mod17),y≡0(mod17)x=12,y2≡7(mod17),無(wú)解x=13,y2≡1(mod17),y≡1,16(mod17)x=14,y2≡5(mod17),無(wú)解x=15,y2≡8(mod17),y≡5,12(mod17)x=16,y2≡16(mod17),y≡4,13(mod17)10．解：(1）.（17/37）=(-1)(17-1)(37-1)/(2*2)*(37/17)=-1(4）.（911/2003）=(-1)(2003-1)(911-1)/(2*2)*(2003/911)=1/3=1(6）.（7/20040803）=(-1)(7-1)(20040803-1)/(2*2)12．解：（1）.因?yàn)椋?2/67）=(65/67)=1所以-2是67的平方剩余*(20040803/7)=1所以x2≡-2(mod67)有2個(gè)解。（4）.因?yàn)椋?/37）=(-1)(37*37-1)/8=-1所以2是37的平方非剩余所以x2≡2(mod37)無(wú)解。14．證明：（1）因?yàn)閜為其素?cái)?shù)，模p的所有二次剩余個(gè)數(shù)為(p-1)/2個(gè)，設(shè)為a1,a2,a3,…a(p-1)/2則a1*a2*a3…a(p-1)/2≡12*22*32…((p-1)/2)2(modp)≡1*2*3…((p-1)/2)*(-(p-1))*(-(p-2))*…(-(p-(p-1)/2))(modp)≡1*2*3…((p-1)/2)*(p-(p-1)/2)…*(p-2)*(p-1)(-1)(p-1)/2(modp)≡(p-1)!*(-1)(p-1)/2(modp)≡(-1)*(-1)(p-1)/2(modp)（2.4定理3）≡(-1)(p+1)/2(modp)所以模p的所有二次剩余乘積模p的剩余為(-1)(p+1)/2（2）1，2，3,…p-1為p的一個(gè)完全剩余系得證。1*2*2…*(p-1)≡-1(modp)≡(-1)(p+1)/2(-1)(p-1)/2(modp)因?yàn)槟的所有二次剩余乘積模p的剩余為(-1)(p+1)/2所以模p的所有非二次剩余乘積模p的剩余為(-1)(p－1)/2（3）當(dāng)p=3時(shí)，其二次剩余只有1，所以p=3時(shí)，模p的所有二次剩余之和模p的剩余為1當(dāng)p>3時(shí)，由（1）得a1+a2+a3…+a(p-1)/2≡p(p-1)(p+1)/24(modp)因?yàn)閜為奇素?cái)?shù)，所以p只能取3k-1或3k+1形式，代入上式得0所以當(dāng)p>3時(shí)，模p的所有二次剩余之和模p的剩余為0。（4）因?yàn)槟的所有二次非剩余之和與所有二次剩余之和的和可以被p整除所以由(3)得，當(dāng)p=3時(shí)，模p的所有二次非剩余之和模p的剩余為-1;當(dāng)p>3時(shí)，模p的所有二次非剩余之和模p的剩余為0。16．解：(1）.因?yàn)椋?/227）=(-1)(227-1)(7-1)/(2*2)*(227/7)=1所以7是227的二次剩余所以x2≡7(mod227)有解(3）.因?yàn)?1對(duì)91的逆元是58所以原同余方程等價(jià)于x2≡16(mod91)又16是91的平方剩余所以11x2≡-6(mod91)有解21．證明：應(yīng)用模重復(fù)平方法11=20+21+23令x=23,b=2,a=1(1)x0=1a0=a*b≡2(mod23)(2)x1=1a1=a0*b1≡8(mod23)b1=b2≡4(mod23)b2=b12≡16(mod23)b3=b22≡3(mod23)(3)x2=0a2=a1*b20≡8(mod23)(4)x3=1a3=a2*b3≡1(mod23)所以211≡1(mod23)即23|211-147|223-1與503|2251-1應(yīng)用同樣的方法得證。第五章．原根與指標(biāo)1．解：因?yàn)?13)=12,所以只需對(duì)12的因數(shù)d=1,2,3,4,6,12,計(jì)算ad(mod12)因?yàn)?1≡2,22≡4,23≡8,24≡3,26≡-1,212≡1(mod13)所以2模13的指數(shù)為12；同理可得：5模13的指數(shù)為4，10模13的指數(shù)為6。2．解：因?yàn)?19)=18,所以只需對(duì)18的因數(shù)d=1,2,3,6,9,18計(jì)算ad(mod12)因?yàn)?1≡3,32≡9,33≡8,36≡7,39≡-1,218≡1(mod13)所以3模19的指數(shù)為18；同理可得：7模19的指數(shù)為3，10模19的指數(shù)為18。3．解：因?yàn)?m)=(81)=54=2*33,所以(m)的素因數(shù)為q1=2,q2=3,進(jìn)而(m)/q1=27,(m)/q2=18這樣，只需驗(yàn)證：g27,g18模m是否同余于1。對(duì)2，4，5，6…逐個(gè)驗(yàn)算：因?yàn)?271(mod81)2181(mod81)根據(jù)5.2定理8得所以2是模81的原根7．證明：因?yàn)椋╝,m）=1,故由ordm(a)=st知：ast≡1(modm)即(as)t≡1(modm)不妨令ordm(as)=r則asr≡1(modm)所以st|sr由(as)t≡1(modm)得r|t即t＝