《2011信息安全数学基础习题答案》由会员分享，可在线阅读，更多相关《2011信息安全数学基础习题答案（14页珍藏版）》请在金锄头文库上搜索。
1、12011 信息安全数学基础习题答案第一章 整数的可除性1证明：因为 2|n 所以 n=2k , k Z5|n 所以 5|2k ， 又（5，2）=1，所以 5|k 即 k=5 k1 ，k 1 Z7|n 所以 7|2*5 k1 ,又（7，10）=1，所以 7| k1 即 k1=7 k2，k 2 Z所以 n=2*5*7 k2 即 n=70 k2, k2 Z因此 70|n2证明：因为 a3-a=(a-1)a(a+1)当 a=3k，k Z 3|a 则 3|a3-a当 a=3k-1，k Z 3|a+1 则 3|a3-a当 a=3k+1，k Z 3|a-1 则 3|a3-a所以 a3-a能被 3整除。3证
2、明：任意奇整数可表示为 2 k0+1， k0 Z（2 k 0+1） 24 k 02+4 k0+1=4 k0 (k0+1)+1由于 k0与 k0+1为两连续整数，必有一个为偶数，所以 k0 (k0+1)=2k所以（2 k 0+1） 2=8k+1 得证。4证明：设三个连续整数为 a-1,a,a+1 则(a-1)a(a+1)= a 3-a由第二题结论 3|（a 3-a） 即 3|(a-1)a(a+1)又三个连续整数中必有至少一个为偶数，则 2|(a-1)a(a+1)又（3，2）=1 所以 6|(a-1)a(a+1) 得证。5证明：构造下列 k个连续正整数列：(k+1)！+2, (k+1)！+3, (
3、k+1)！+4, (k+1)！+(k+1), k Z对数列中任一数 (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 为合数所以此 k个连续正整数都是合数。6证明：因为 1911/214 ,小于 14的素数有 2，3，5，7，11，13经验算都不能整除 191 所以 191为素数。因为 5471/224 ,小于 24的素数有 2，3，5，7，11，13，17，19，23经验算都不能整除 547 所以 547为素数。由 737=11*67 ,747=3*249 知 737与 747都为合数。8解：存在。eg
4、：a=6,b=2,c=910证明：p 1 p2 p3|n， 则 n= p1 p2 p3k，k N+又 p1 p 2 p 3，所以 n= p1 p2 p3kp 13 即 p13n 1/3p1为素数 则 p12，又 p1 p 2 p 3，所以 n= p1 p2 p3k2 p 2 p32p 22 即 p2(n/2) 1/2 得证。11解：小于等于 5001/2的所有素数为 2，3，5，7，11，13，17，19，依次删除这些素数的倍数可得所求素数：12证明：反证法假设 3k+1没有相同形式的素因数，则它一定只能表示成若干形如 3k-1的素数相乘。 (3 k1+1)(3 k2+1)=( 3 k1+1)
5、 k2+ k1*3+1 显然若干个 3k+1的素数相乘，得到的还是 3k+1的形式，不能得出 3k-1的数，因此假设不成立，结论得证。同理可证其他。13证明：反证法假设形如 4k+3的素数只有有限个，记为 p1, p2, pn因为 4k+3=4k-1=4k-1 构造 N=4*p1*p2*pn-13 *p1*p2*pn所以 Np i (i=1,2,n) N为 4k-1形式的素数，即为 4k+3的形式，所以假设不成立。原结论正确，形如 4k+3的素数有无穷多个。28 （1）解：85=1*55+30255=1*30+2530=1*25+525=5*5所以(55,85)=5（2）解：282=1*202
6、+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
7、)=551*3589+(-1226)*1613所以 s=-1226 t=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=951 t=-74336证明：因为（a，4）=2 所以 a=2*(2m+1) m Z所以 a+b=4m+2+4n
8、+2=4(m+n)+4=4(m+n+1)即 4|a+b所以（a+b,4）=437证明：反证法假设 n为素数，则 n| a2- b2=(a+b)(a-b)由 1.4定理 2知 n|a+b或 n|a-b,与已知条件矛盾所以假设不成立，原结论正确，n 为合数。40证明：（1）假设是 21/2有理数，则存在正整数 p，q，使得 21/2=p/q,且（p, q）=1平方得：p 2=2q2, 即 2|p2，所以 p=2m, m N3因此 p2=4m2=2q2 q2=2m2 q=2n, n N则（p, q）=(2m,2n)=2(m, n)2 与（p, q）=1 矛盾所以假设不成立，原结论正确，2 1/2不是
9、有理数。（2）假设是 71/2有理数，则存在正整数 m，n，使得 71/2=p/q,且（m, n）=1平方得：m 2=2n2, 即 7|m2将 m表示成 n个素数 pi 的乘积，m= p 1 p2 p3 pn ， pi 为素数。因为 7 为素数，假设 7 !| m，则 7 !p 1 ，p 2，p 3 ，p n所以 m2= p12 p22 p32 pn 2=( p1 p2 p3 pn)( p1 p2 p3 pn)所以 7 !| m2，与 7|m2矛盾，故 7|m, m=7k同理可知：7|n, n=7 k 0所以(m, n)=(7k,7 k 0)=7(k, k0)7 与已知矛盾故原结论正确，7 1
10、/2不是有理数。（3）同理可证 171/2不是有理数。41证明：假设 log210是有理数，则存在正整数 p, q,使得 log210=p/q,且（p, q）=1又 log210=ln10/ln2=p/q Ln10q=ln2p 10q=2p(2*5)q=2p 5q=2p-q所以只有当 q=p=0是成立，所以假设不成立故原结论正确，log 210是无理数。同理可证 log37，log 1521都是无理数。50 （1）解：因为 8=23, 60=22*3*5所以8,60=2 3*3*5=12051 （4）解：(47 1179111011001,4111831111011000)= 41047079
11、08301011000=1011000471179111011001,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）中的要求对模 10不能实现。2证明：当 m2时，因为(m-1) 2=m2-2m+1=m(m-2)+1所以(m-1) 21(mod m)即 1与(m-1) 2在同一个剩余类中，故 02,12,(m-1)2一定不是模 m的完全剩余系。6解：2 12(mod7), 2 24(
12、mod7), 2 31(mod7)又 20080509=6693503*3所以 220080509=(23)66935031(mod7)故 220080509是星期六。7证明：（i）因为 ai b i (modm),1ik 所以 ai=bi+kim又 a1+a2+ +ak=a i=(b i+kim)=b i+m*k i所以有a ib i (mod m)即 a1+a2+ +ak=b1+b2+ +bk (mod m)（ii）因为 ai b i (mod m),1ik 所以 ai(mod m)=bi (mod m)所以（a 1a2ak）mod m(a 1mod m)( a2mod m)(ak mod
13、 m)mod m(b 1mod m)( b2mod m)(bk mod m)mod m（b 1b2bk）mod m所以 a 1a2aka 1a2ak(mod m)8证明：如果 a2b 2(mod p) 则 a2= b2+kp , k Z 即 kp=a2-b2=(a+b)(a-b) 所以 p|(a+b)(a-b) 又 p为素数，根据 1.4定理 2知 p|a+b或 p|a-b 得证。49证明：如果 a2b 2(mod n) 则 a2= b2+kn , k Z 即 kn=a2-b2=(a+b)(a-b) 所以 n|(a+b)(a-b) 由 n=pq知 kpq=a2-b2=(a+b)(a-b)因为
14、n!|a-b, n!|a+b，所以 p,q不能同时为 a-b或 a+b的素因数。不妨设 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)=p1(n, a+b)=(pq, a+b)=(q, a+b)=q1故原命题成立。10证明：因为 ab (mod c) 则 a=cq+b , q Z根据 1.3定理 3知(a, c)=(b, c)17解：（1）a k+ak-1+ +a0=1+8+4+3+5+8+1=30因为 3|30 ,9!|30 所以 1843581能被 3整除，不能被 9整除。
15、（2）a k+ak-1+ +a0=1+8+4+2+3+4+0+8+1=31因为 3!|31 , 9!|31 所以 184234081不能被 3整除，也不能被 9整除。（3）a k+ak-1+ +a0=8+9+3+7+7+5+2+7+4+4=56因为 3!|56 , 9!|56 所以 8937752744不能被 3整除，也不能被 9整除。（4）a k+ak-1+ +a0=4+1+5+3+7+6+8+9+1+2+2+4+6=58因为 3!|58 , 9!|58 所以 4153768912246不能被 3整除，也不能被 9整除。20解：（89878*58965）mod9(89878mod9)*(58965mod9)mod9(4*6)mod96(mod9) 5299?56270(mod9)又 5299?56270(45+?)mod9?(mod9)所以 ?=6 即未知数字为 6。21解：（1）因为 875961*2753(36mod9)(17mod9)mod9 0(mod9)241052063326(mod9) 8(mod9)所以等式 87596
