信息安全数学基础习题答案.docx
《信息安全数学基础习题答案.docx》由会员分享，可在线阅读，更多相关《信息安全数学基础习题答案.docx（21页珍藏版）》请在冰点文库上搜索。
信息安全数学基础习题答案
信息安全数学基础习题答案
第一章整数的可除性
1．证明：
因为2|n所以n=2k,k
Z
5|n所以5|2k，又（5，2）=1，所以5|k即k=5k1，k1
Z
7|n所以7|2*5k1,又（7，10）=1，所以7|k1即k1=7k2，k2
Z
所以n=2*5*7k2即n=70k2,k2
Z
因此70|n
2．证明：
因为a3-a=（a-1）a（a+1）
当a=3k，k
Z3|a则3|a3-a
当a=3k-1，k
Z3|a+1则3|a3-a
当a=3k+1，k
Z3|a-1则3|a3-a
所以a3-a能被3整除。
3．证明：
任意奇整数可表示为2k0+1，k0
Z
（2k0+1）2＝4k02+4k0+1=4k0（k0+1）+1
由于k0与k0+1为两连续整数，必有一个为偶数，所以k0（k0+1）=2k
所以（2k0+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=9
10．证明：
p1p2p3|n，则n=p1p2p3k，k
N+
又p1≤p2≤p3，所以n=p1p2p3k≥p13即p13≤n1/3
p1为素数则p1≥2，又p1≤p2≤p3，所以n=p1p2p3k≥2p2p3≥2p22
即p2≤（n/2）1/2得证。
11．解：
小于等于5001/2的所有素数为2，3，5，7，11，13，17，19，依次删除这些素数的倍数可得所求素数：
12．证明：
反证法
假设3k+1没有相同形式的素因数，则它一定只能表示成若干形如3k-1的素数相乘。
（3k1+1）（3k2+1）=[（3k1+1）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-1≥3*p1*p2*…*pn
所以N＞pi（i=1,2,…,n）
N为4k-1形式的素数，即为4k+3的形式，所以假设不成立。
原结论正确，形如4k+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）*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=-743
36．证明：
因为（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）=4
37．证明：
反证法
假设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=2q2q2=2m2q=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
将m表示成n个素数pi的乘积，m=p1p2p3……pn，pi为素数。
因为7为素数，假设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与已知矛盾
故原结论正确，71/2不是有理数。
（3）同理可证171/2不是有理数。
41．证明：
假设log210是有理数，则存在正整数p,q,使得log210=p/q,且（p,q）=1
又log210=ln10/ln2=p/q
Ln10q=ln2p10q=2p
（2*5）q=2p5q=2p-q
所以只有当q=p=0是成立，所以假设不成立
故原结论正确，log210是无理数。
同理可证log37，log1521都是无理数。
50．
（1）解：
因为8=23,60=22*3*5
所以[8,60]=23*3*5=120
51．（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（modm）
即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）因为ai≡bi（modm）,1≤i≤k所以ai=bi+kim
又a1+a2+…+ak=∑ai=∑（bi+kim）=∑bi+m*∑ki
所以有∑ai≡∑bi（modm）
即a1+a2+…+ak=b1+b2+…+bk（modm）
（ii）因为ai≡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,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（modn）则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（modc）则a=cq+b,q
Z
根据1.3定理3知（a,c）=（b,c）
17．解：
（1）ak+ak-1+…+a0=1+8+4+3+5+8+1=30
因为3|30,9!
|30所以1843581能被3整除，不能被9整除。
（2）ak+ak-1+…+a0=1+8+4+2+3+4+0+8+1=31
因为3!
|31,9!
|31所以184234081不能被3整除，也不能被9整除。
（3）ak+ak-1+…+a0=8+9+3+7+7+5+2+7+4+4=56
因为3!
|56,9!
|56所以8937752744不能被3整除，也不能被9整除。
（4）ak+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）mod9
≡6（mod9）≡5299?
56270（mod9）
又5299?
56270≡（45+?
）mod9≡?
（mod9）
所以?
=6即未知数字为6。
21．解：
（1）因为875961*2753≡[（36mod9）（17mod9）]mod9≡0（mod9）
2410520633≡26（mod9）≡8（mod9）
所以等式875961*2753=2410520633不成立
（2）因为14789*23567≡[（29mod9）（23mod9）]mod9≡1（mod9）
348532367≡41（mod9）≡5（mod9）
所以等式14789*23567=348532367不成立
（3）因为24789*43717≡[（30mod9）（22mod9）]mod9≡3（mod9）
1092700713≡30（mod9）≡3（mod9）
所以等式24789*43717=1092700713可能成立
（4）这种判断对于判断等式不成立时简单明了，但对于判断等式成立时，可能会较复杂。
22．解：
因为7为素数，由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．证明：
因为c1,c2,…,c
（m）是模m的简化剩余系
对于任一ci，有m-ci也属于模m的简化剩余系
所以ci+（m-ci）≡0（modm）
因此c1+c2+…+c
（m）≡0（modm）
32．证明：
因为a
（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．证明：
因为7为素数，由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．证明：
因为32760=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）
a
（8）≡a4≡1（mod8）即a12≡1（mod8）
a
（5）≡a4≡1（mod5）即a12≡1（mod5）
a
（7）≡a6≡1（mod7）即a12≡1（mod7）
a
（9）≡a6≡1（mod9）即a12≡1（mod9）
又因为[5,7,8,9,13]=32760
所以a12≡1（mod32760）
35．证明：
因为（p,q）=1p,q都为素数所以
（p）=p-1,
（q）=q-1
由Euler定理知：
p
（q）≡1（modq）q
（p）≡1（modp）
即pq-1≡1（modq）qp-1≡1（modp）
又qp-1≡0（modq）pq-1≡0（modp）
所以pq-1+qp-1≡1（modq）qp-1+pq-1≡1（modp）
又[p,q]=pq所以pq-1+qp-1≡1（modpq）
36．证明：
因为（m,n）=1
由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）解：
因为（3，7）=1|2故原同余式有解
又3x≡1（mod7）所以特解x0`≡5（mod7）
同余式3x≡2（mod7）的一个特解x0≡2*x0`=2*5≡3（mod7）
所有解为：
x≡3（mod7）
（3）解：
因为（17，21）=1|14故原同余式有解
又17x≡1（mod21）所以特解x0`≡5（mod21）
同余式17x≡14（mod21）的一个特解x0≡14*x0`=14*5≡7（mod21）
所有解为：
x≡7（mod21）
2．
（1）解：
因为（127，1012）=1|833故原同余式有解
又127x≡1（mod1012）所以特解x0`≡255（mod1012）
同余式127x≡833（mod1012）的一个特解x0≡833*x0`=833*255≡907（mod1012）
所有解为：
x≡907（mod1012）
3．见课本3.2例1
7．
（1）解：
因为（5，14）=1
由Euler定理知，同余方程5x≡3（mod14）的解为：
x≡5
（14）-1*3≡9（mod14）
（2）解：
因为（4，15）=1
由Euler定理知，同余方程4x≡7（mod15）的解为：
x≡4
（15）-1*7≡13（mod15）
（3）解：
因为（3，16）=1
由Euler定理知，同余方程3x≡5（mod16）的解为：
x≡3
（16）-1*5≡7（mod16）
11．证明：
由中国剩余定理知方程解为：
x≡a1M1M1`+a2M2M2`+……+akMkMk`（modm）
因为mi两两互素，又中国剩余定理知：
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例4
14．同课本3.2例321000000≡562（mod1309）
15．
（1）解：
等价同余式组为：
23x≡1（mod4）
23x≡1（mod5）
23x≡1（mod7）
所以x≡3（mod4）x≡2（mod5）x≡4（mod7）
所以x≡3*35*3+2*28*2+4*20*6≡67（mod140）
（2）解：
等价同余式组为：
17x≡1（mod4）
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
所以原同余式可化简为：
x6+2x5+2x2+15x2+5x≡0（mod7）
直接验算得解为：
x≡0（mod7）x≡6（mod7）
20．解：
f`（x）≡4x3+7（mod243）
直接验算的同余式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．解：
对x=0,1,2,3,4,5,6时，分别求出y
x=0,y2≡1（mod7）,y≡1,6（mod7）
x=4,y2≡4（mod7）,y≡2,5（mod7）
当x=1,2,3,5,6时均无解
5．解：
对x=0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16时，分别求出y
x=0,y2≡1（mod17）,y≡1,16（mod17）
x=1,y2≡3（mod17）,无解
x=2,y2≡11（mod17）,无解
x=3,y2≡14（mod17）,无解
x=4,y2≡1（mod17）,y≡1,16（mod17）
x=5,y2≡12（mod17）,无解
x=6,y2≡2（mod17）,y≡6,11（mod17）
x=7,y2≡11（mod17）,无解
x=8,y2≡11（mod17）,无解
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）,无解
x=13,y2≡1（mod17）,y≡1,16（mod17）
x=14,y2≡5（mod17）,无解
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）*（20040803/7）=1
12．解：
（1）.因为（-2/67）=（65/67）=1
所以-2是67的平方剩余
所以x2≡-2（mod67）有2个解。
（4）.因为（2/37）=（-1）（37*37-1）/8=-1
所以2是37的平方非剩余
所以x2≡2（mod37）无解。
14．证明：
（1）因为p为其素数，模p的所有二次剩余个数为（p-1）/2个，
设为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的一个完全剩余系
1*2*2…*（p-1）≡-1（modp）≡（-1）（p+1）/2（-1）（p-1）/2（modp）
因为模p的所有二次剩余乘积模p的剩余为（-
升级会员 