信息安全数学基础习题答案
第一章 整数的可除性
1.证明:因为 2|n
所以 n=2k , kZ
5|n 所以 5|2k , 又(5,2)=1,所以 5|k 即 k=5 k1 ,k1Z
7|n 所以 7|2*5 k1 ,又(7,10)=1,所以 7| k1 即 k1=7 k2,k2 Z
所以 n=2*5*7 k2 即 n=70 k2,
因此 70|n
k2 Z
2.证明:因为 a3-a=(a-1)a(a+1)
则 3|a3-a
3|a
3|a+1 则 3|a3-a
3|a-1 则 3|a3-a
当 a=3k,kZ
当 a=3k-1,kZ
当 a=3k+1,kZ
所以 a3-a 能被 3 整除。
3.证明:任意奇整数可表示为 2 k0+1, k0Z
2+4 k0+1=4 k0 (k0+1)+1
(2 k0+1)2=4 k0
由于 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)
又三个连续整数中必有至少一个为偶数,则 2|(a-1)a(a+1)
又(3,2)=1 所以 6|(a-1)a(a+1) 得证。
即 3|(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
经验算都不能整除 547 所以 547 为素数。
由 737=11*67 ,747=3*249 知 737 与 747 都为合数。
,小于 24 的素数有 2,3,5,7,11,13,17,19,23
8.解:存在。eg:a=6,b=2,c=9
10.证明:p1 p2 p3|n, 则 n= p1 p2 p3k,kN+
又 p1≤ p2 ≤p3,所以 n= p1 p2 p3k≥p1
p1 为素数 则 p1≥2,又 p1≤ p2 ≤p3,所以 n= p1 p2 p3k≥2 p2 p3≥2p2
即 p2≤(n/2)1/2
3 即 p1
得证。
3≤n1/3
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 的素数相乘,得
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
N 为 4k-1 形式的素数,即为 4k+3 的形式,所以假设不成立。
原结论正确,形如 4k+3 的素数有无穷多个。
(i=1,2,…,n)
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=-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)
2
=951*2947+(-743)*3772
t=-743
所以 s=951
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, mN
q=2n, nN
因此 p2=4m2=2q2
则(p, q)=(2m,2n)=2(m, n)≥2 与(p, q)=1 矛盾
所以假设不成立,原结论正确,21/2 不是有理数。
q2=2m2
(2)假设是 71/2 有理数,则存在正整数 m,n,使得 71/2=p/q,且(m, n)=1
平方得:m2=2n2, 即 7|m2
将 m 表示成 n 个素数 pi 的乘积,m= p1 p2 p3 ……pn , pi 为素数。
因为 7 为素数,假设 7 !| m,则 7 !∈{p1 ,p2,p3 ,……pn}
2 p2
2 p3
2=( p1 p2 p3 ……pn)( p1 p2 p3 ……pn)
2 ……pn
所以 m2= p1
所以 7 !| m2,与 7|m2 矛盾,故 7|m,
同理可知:7|n,
n=7 k0
m=7k
所以(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/q
10q=2p
Ln10q=ln2p
5q=2p-q
(2*5)q=2p
所以只有当 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
第二章.同余
3
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)因为 ai≡ bi (modm),1≤i≤k
所以 ai=bi+kim
又 a1+a2+… +ak=∑ai=∑(bi+kim)=∑bi+m*∑ki
所以有∑ai≡∑bi (mod m)
即 a1+a2+… +ak=b1+b2+… +bk (mod m)
(ii)因为 ai≡ bi (mod m),1≤i≤k 所以 ai(mod m)=bi (mod m)
所以(a1a2…ak)mod m≡[(a1mod m)( a2mod m)…(ak mod m)]mod m
≡[(b1mod m)( b2mod m)…(bk mod m)]mod m
≡(b1b2…bk)mod m
所以 a1a2…ak≡a1a2…ak(mod m)
8.证明:如果 a2≡b2(mod p)
则 a2= b2+kp , kZ
即 kp=a2-b2=(a+b)(a-b)
又 p 为素数,根据 1.4 定理 2 知 p|a+b 或 p|a-b 得证。
所以 p|(a+b)(a-b)
9.证明:如果 a2≡b2(mod n)
则 a2= b2+kn , kZ
所以 n|(a+b)(a-b)
即 kn=a2-b2=(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 , qZ
根据 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。
4
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)=1
p,q 都为素数 所以(p)=p-1, (q)=q-1
由 Euler 定理知:p(q)≡1(modq)
q(p)≡1(modp)
即 pq-1≡1(modq)
又 qp-1≡0(modq)
qp-1≡1(modp)
pq-1≡0(modp)
所以 pq-1+qp-1≡1(modq)
又[p,q]=pq 所以 pq-1+qp-1≡1(modpq)
qp-1+pq-1≡1(modp)
36.证明:因为(m,n)=1
由 Euler 定理知:m(n)≡1(modn)
所以 m(n)+n(m)≡(m(n)modn)+ (n(m)modn)≡1+0≡1(modn)
同理有:m(n)+n(m) ≡1(modm)
n(m)≡1(modm)
5
又[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`(mod m)
因为 mi 两两互素,又中国剩余定理知:MiMi`≡1(mod mi)
又 Mi=m/mi 所以(m,Mi)≡1(mod mi)
所以 MiMi`=Mi(mi)≡(mod mi)
代入方程解为 x≡a1 M1(m1)+ a2 M2(m2)+……+ ak Mk(mk)(mod m) 得证。
12.(1)解:由方程组得:3x+3y≡2(mod7)
6x+6y≡4(mod7)
x+y≡-4(mod7)
X≡5(mod 7)
y≡5 (mod 7)
(2)解:由方程组得:2x+6y≡2(mod7)
6x+8y≡4(mod7)
2x-y≡2(mod7)
x-y≡-4(mod7)
X≡6(mod 7)
y≡3 (mod 7)
13.见课本 3.2 例 4
14.同课本 3.2 例 3
15.(1)解:等价同余式组为:
21000000≡562(mod1309)
23x≡1(mod4)
6
23x≡1(mod5)
23x≡1(mod7)
所以 x≡3(mod4)
所以 x≡3*35*3 + 2*28*2 + 4*20*6≡67(mod140)
x≡2(mod5)
x≡4(mod7)
(2)解:等价同余式组为:
17x≡1(mod4)
17x≡1(mod5)
17x≡1(mod7)
17x≡1(mod11)
所以 x≡1(mod4)
所以 x≡1*385*1 + 2*308*2 + (-3)*220*5 + 7*140*7 ≡557(mod1540)
x≡-3(mod7)
x≡2(mod5)
x≡7(mod11)
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)
所以 t1≡-f(x1)*( f`(x1)-1(mod3))/31≡1(mod 3)
f`(x1)-1≡-1(mod3)
x2≡ x1+3 t1≡4(mod 9)
t2≡-f(x2)*( f`(x1)-1(mod3))/32≡2(mod 3)
x3≡ x2+32 t2≡22(mod 27)
t3≡-f(x3)*( f`(x1)-1(mod3))/33≡0(mod 3)
x4≡ x3+33 t3≡22(mod 81)
t5≡-f(x4)*( f`(x1)-1(mod3))/34≡2(mod 3)
x5≡ x4+34 t4≡184(mod 243)
所以同余式 f(x)≡0(mod243)的解为:x5 ≡184(mod 243)
第四章.二次同余式与平方剩余
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)
7
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(mod p)
≡1*2*3…((p-1)/2)*(-(p-1))*(-(p-2))*…(-(p-(p-1)/2))(mod p)
≡1*2*3…((p-1)/2)*(p-(p-1)/2)…*(p-2)*(p-1)(-1)(p-1)/2(mod p)
≡(p-1)!*(-1)(p-1)/2(mod p)
≡(-1)*(-1)(p-1)/2(mod p)
≡(-1)(p+1)/2(mod p)
所以模 p 的所有二次剩余乘积模 p 的剩余为(-1)(p+1)/2 得证。
(2.4 定理 3)
(2)1,2,3,…p-1 为 p 的一个完全剩余系
1*2*2…*(p-1)≡-1(mod p) ≡(-1)(p+1)/2(-1)(p-1)/2(mod p)
因为模 p 的所有二次剩余乘积模 p 的剩余为(-1)(p+1)/2
所以模 p 的所有非二次剩余乘积模 p 的剩余为(-1)(p-1)/2
(3)当 p=3 时,其二次剩余只有 1,所以 p=3 时,模 p 的所有二次剩余之和模 p
的剩余为 1
当 p>3 时,由(1)得 a1+a2+a3…+a(p-1)/2≡p(p-1)(p+1)/24(mod p)
因为 p 为奇素数,所以 p 只能取 3k-1 或 3k+1 形式,代入上式得 0
所以当 p>3 时,模 p 的所有二次剩余之和模 p 的剩余为 0。
(4)因为模 p 的所有二次非剩余之和与所有二次剩余之和的和可以被 p 整除
所以由(3)得,当 p=3 时,模 p 的所有二次非剩余之和模 p 的剩余为-1;
当 p>3 时,模 p 的所有二次非剩余之和模 p 的剩余为 0。
16.解:(1).因为(7/227)=(-1) (227-1)(7-1)/(2*2)*(227/7)= 1
所以 7 是 227 的二次剩余
所以 x2≡7(mod227)有解
(3).因为 11 对 91 的逆元是 58
8