信息安全数学基础习题答案第一章整数的可除性1．证明：因为2|n 所以n=2k , k∈Z5|n 所以5|2k ，又（5，2）=1，所以5|k 即k=5 k1，k1∈Z7|n 所以7|2*5 k1 ,又（7，10）=1，所以7| k1即k1=7 k2，k2∈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 k0+1，k0∈Z（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∈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=910．证明：p1 p2 p3|n，则n= p1 p2 p3k，k∈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的素数有无穷多个。
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=-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+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=m/n,且（m, n）=1 平方得：m2=7n2, 即7|m2将m表示成n个素数p i的乘积，m= p1 p2 p3……p n ，p i为素数。
因为7为素数，假设7 !| m，则7 !∈｛p1，p2，p3，……p n｝所以m2= p12 p22 p32……p n 2=( p1 p2 p3……p n)( p1 p2 p3……p n)所以7 !| m2，与7|m2矛盾，故7|m, m=7k同理可知：7|n, n=7 k0所以(m, n)=(7k,7 k0)=7(k, k0)≥7 与已知矛盾故原结论正确，71/2不是有理数。
（3）同理可证171/2不是有理数。
41．证明：假设log210是有理数，则存在正整数p, q,使得log210=p/q,且（p, q）=1 又log210=ln10/ln2=p/qLn10q=ln2p 10q=2p(2*5)q=2p 5q=2p-q所以只有当q=p=0是成立，所以假设不成立故原结论正确，log210是无理数。
同理可证log37，log1521都是无理数。
50．（1）解：因为8=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）中的要求对模10不能实现。
2．证明：当m>2时，因为(m-1)2=m2-2m+1=m(m-2)+1所以(m-1)2≡1(mod m)即1与(m-1)2在同一个剩余类中，故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）因为a i≡b i (modm),1≤i≤k 所以a i=b i+k i m又a1+a2+… +a k=∑a i=∑(b i+k i m)=∑b i+m*∑k i所以有∑a i≡∑b i (mod m)即a1+a2+… +a k=b1+b2+… +b k (mod m)（ii）因为a i≡b i (mod m),1≤i≤k 所以a i(mod m)=b i (mod m)所以（a1a2…a k）mod m≡[(a1mod m)( a2mod m)…(a k mod m)]mod m≡[(b1mod m)( b2mod m)…(b k mod m)]mod m≡（b1b2…b k）mod m所以a1a2…a k≡a1a2…a k(mod m)8．证明：如果a2≡b2(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 得证。
9．证明：如果a2≡b2(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)因为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)=p>1(n, a+b)=(pq, a+b)=(q, a+b)=q>1故原命题成立。
10．证明：因为a≡b (mod c) 则a=cq+b , q∈Z根据1.3定理3知(a, c)=(b, c)17．解：（1）a k+a k-1+… +a0=1+8+4+3+5+8+1=30因为3|30 ,9!|30 所以1843581能被3整除，不能被9整除。
（2）a k+a k-1+… +a0=1+8+4+2+3+4+0+8+1=31因为3!|31 , 9!|31 所以184234081不能被3整除，也不能被9整除。
（3）a k+a k-1+… +a0=8+9+3+7+7+5+2+7+4+4=56因为3!|56 , 9!|56 所以8937752744不能被3整除，也不能被9整除。
（4）a k+a k-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)mod9≡6(mod9) ≡5299?56270(mod9)又5299?56270≡(45+?)mod9≡?(mod9)所以 ?=6 即未知数字为6。