当前位置:文档之家› 最新。信息安全数学基础习题答案

最新。信息安全数学基础习题答案

信息安全数学基础习题答案第一章整数的可除性1.证明1:因为2|n 所以n=2k , k1Z5|n 所以5|2k ,又(5,2)=1,所以5|k 即k=5 k1,k11Z7|n 所以7|2*5 k1 ,又(7,10)=1,所以7| k1即k1=7 k2,k21Z所以n=2*5*7 k2即n=70 k2, k21Z因此70|n证明2:n是2、5、7的公倍数,所以[2,5,7]|n,又知2、5、7互素,所以[2,5,7]=2*5*7=70,即70|n。

2.证明:因为a3-a=(a-1)a(a+1)当a=3k,k22(mod)a b p≡Z 3|a 则3|a3-a当a=3k-1,k p a b-Z 3|a+1 则3|a3-a当a=3k+1,k p a b+Z 3|a-1 则3|a3-a所以a3-a能被3整除。

3.证明:任意奇整数可表示为2 k0+1, k022(mod)≡Za b p(2 k0+1)2=4 k02+4 k0+1=4 k0 (k0+1)+1由于k0与k0+1为两连续整数,必有一个为偶数,所以k0 (k0+1)=2k所以(2 k0+1)2=8k+1 得证。

4.证明:设三个连续整数为a-1,a,a+1 则(a-1)a(a+1)= a3-a由第二题结论3|(a3-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, (k+1)!+4,……, (k+1)!+(k+1), k p a b-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/2<14 ,小于14的素数有2,3,5,7,11,13经验算都不能整除191 所以191为素数。

因为5471/2<24 ,小于24的素数有2,3,5,7,11,13,17,19,23经验算都不能整除547 所以547为素数。

由737=11*67 ,747=3*249 知737与747都为合数。

8.解:存在。

eg:a=6,b=2,c=99.证明:反证,设n/p是合数,n/p= k1k2, k1>p, k2>p,则n=p k1k2> n3,所以p< n1/3,矛盾。

10.证明:p1 p2 p3|n,则n= p1 p2 p3k,k p a b+N+又p1≤ p2≤p3,所以n= p1 p2 p3k≥p13 即p13≤n1/3p1为素数则p1≥2,又p1≤ p2≤p3,所以n= p1 p2 p3k≥2 p2 p3≥2p22即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) k2+ k1]*3+1 显然若干个3k+1的素数相乘,得到的还是3k+1的形式,不能得出3k-1的数,因此假设不成立,结论得证。

同理可证其他。

13.证明:反证法假设形如4k+3的素数只有有限个,记为p1, p2,…, p n因为4k+3=4k`-1=4k-1 构造N=4*p1*p2*…*p n-1≥3*p1*p2*…*p n所以N>p i (i=1,2,…,n)N为4k-1形式的素数,即为4k+3的形式,所以假设不成立。

原结论正确,形如4k+3的素数有无穷多个。

21.证:令此合数为S ,根据此合数的结构特点,我们可构造一个整数M ,使MS 不是整数,从而证明S 不是整数。

(1)k-1k 00k-1011111+++++M=2357k 2234n,p n n n 2,M M M MS=M++++++23n nM M 357M=235723p n 2MS S k S p n M M M pp =⋅⋅⋅≤=⋅⋅⋅⋅⋅=∴令取这里是使最大的整数,是不大于的最大奇数。

则在1,2,3,,中必存在一个所以由知,,,必为整数,显然不是整数。

不是整数,从而不是整数。

28.(1)解:85=1*55+30 55=1*30+25 30=1*25+5 25=5*5 所以(55,85)=5(2)解:282=1*202+80 202=2*80+42 80=1*42+38 42=1*38+4 38=9*4+2 4=2*2所以(202,282)=2 29.(1)解:2t+1=1*(2t-1)+2 2t-1=(t-1)*2+1 2=2*1所以(2t+1,2t-1)=1 (2)解:2(n+1)=1*2n+2 2n=n*2所以(2n,2(n+1))=2 32.(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)*1613j sj-1 sj tj-1 tj qj rj rj+1 1 0 3589 1613 1 1 0 0 1 2 1613 363 2 0 1 1 -2 4 363 161 3 1 -4 -2 9 2 161 41 4 -4 9 9 -20 3 41 38 5 9 -31 -20 69 1 38 3 6 -31 40 69 -89 12 3 2 7 40 -511 -89 1137 1 2 1 8-5115511137-122621所以s=-1226 t=551 (3589,1613)=1(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=-743(3)j sj-1 sj tj-1 tj qj rj rj+11 0 37516 200411 1 0 0 1 1 20041 174752 0 1 1 -1 1 17475 25663 1 -1 -1 2 6 2566 20794 -1 7 2 -13 1 2079 4875 7 -8 -13 15 4 487 1316 8 39 15 -73 3 131 947 39 -125 -73 234 1 94 378 -125 164 234 -307 2 37 209 164 -453 -307 848 1 20 1710 -453 617 848 -1155 1 17 311 617 -1070 -1155 2003 5 3 212 -1070 5967 2003 11170 1 2 113 5967 7037 11170 -9167 2 1 0 所以,s=7037 t=-916736.证明:因为(a,4)=2 所以a=2*(2m+1) m Z所以a+b=4m+2+4n+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平方得:p2=2q2, 即2|p2,所以p=2m, m N因此p2=4m2=2q2 q2=2m2 q=2n, n N则(p, q)=(2m,2n)=2(m, n)≥2与(p, q)=1矛盾所以假设不成立,原结论正确,21/2不是有理数。

(2)假设是71/2有理数,则存在正整数m,n,使得71/2=p/q,且(m, n)=1平方得:m2=2n2, 即7|m2 →7|m同理可知:7|n, n=7 k0所以(m, n)=(7k,7 k0)=7(k, k0)≥7 与已知矛盾故原结论正确,71/2不是有理数。

(3)同理可证171/2不是有理数。

41.证明:假设log 210是有理数,则存在正整数p, q,使得log 210=p/q,且(p, q )=12p/q=10 2p=2q(2*5)q=2p5q=2p-q所以只有当q=p=0是成立,所以假设不成立 故原结论正确,log 210是无理数。

同理可证log 37,log 1521都是无理数。

44.令1212n=p p p s s ααα,若存在i k α=,则取11121211a=p p p p p ,p k k sk k s k b ααααα-+-+=。

n=k ab ∴否则设,0i i iik kq r r α=+≤<,则1212121212121212121212n=p p p =(p p p )(p p p ),p p p ,p p p k k k q q q q q q r r r r r r s s s s q q q a a a s sk s s s s s b +++=令a=n=k ab ∴121211212d=p p p ,d |a,k r ,,k r 0,1,s k s ss d ββββββββ≤≤∴====∴=设若则矛盾。

50.(1)解:因为8=23, 60=22*3*5 所以[8,60]=23*3*5=120 51.(4)解:(471179111011001,4111831111011000)= 410470*********1000=1011000[471179111011001,4111831111011000]= 4111471179111831111011001第二章.同余1.解:(1)其中之一为1,11,3,13,5,15,15,7,17 (2)其中之一为0,10,20,30,40,50,60,70,80(3).(1)或(2)中的要求对模10不能实现。

因为某个数加10不改变奇偶性。

2.证明:(m-i)2=m 2-2mi+ i 2∴(m-i)2≡i 2mod m当m>2时,因为(m-1)2=m 2-2m+1=m(m-2)+1所以(m-1)2≡1(mod m)即1与(m-1)2在同一个剩余类中,故02,12,…,(m-1)2一定不是模m 的完全剩余系。

相关主题