信息安全数学基础习题答案
第一章 整数的可除性
1．证明：因为2|n 所以n=2k , k?Z
5|n 所以5|2k ， 又（5，2）=1，所以5|k 即k=5 k1 ，k1?Z 7|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|n
3
2．证明：因为a-a=(a-1)a(a+1)
3
当a=3k，k?Z 3|a 则3|a-a
3
当a=3k-1，k?Z 3|a+1 则3|a-a
3
当a=3k+1，k?Z 3|a-1 则3|a-a
3
所以a-a能被3整除。
3．证明：任意奇整数可表示为2 k0+1， k0?Z
22
（2 k0+1）＝4 k0+4 k0+1=4 k0 (k0+1)+1
由于k0与k0+1为两连续整数，必有一个为偶数，所以k0 (k0+1)=2k
2
所以（2 k0+1）=8k+1 得证。
3
4．证明：设三个连续整数为a-1,a,a+1 则(a-1)a(a+1)= a-a
3
由第二题结论3|（a-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个连续正整数都是合数。
1/2
6．证明：因为191＜14 ,小于14的素数有2，3，5，7，11，13 经验算都不能整除191 所以191为素数。
1/2
因为547＜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．证明：p1 p2 p3|n， 则n= p1 p2 p3k，k?N
3 31/3
又p1≤ p2 ≤p3，所以n= p1 p2 p3k≥p1 即p1≤n
2
p1为素数 则p1≥2，又p1≤ p2 ≤p3，所以n= p1 p2 p3k≥2 p2 p3≥2p2
1/2
即p2≤(n/2) 得证。
1/2
11．解：小于等于500的所有素数为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的数，因此假设不成立，结论得证。
同理可证其他。
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=-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=-743
2
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．证明：反证法
22
假设n为素数，则n| a- b=(a+b)(a-b)
由1.4定理2知n|a+b或n|a-b,与已知条件矛盾 所以假设不成立，原结论正确，n为合数。
1/21/2
40．证明：（1）假设是2有理数，则存在正整数p，q，使得2=p/q,且（p, q）=1
222
平方得：p=2q, 即2|p，所以p=2m, m?N
22222
因此p=4m=2q q=2m q=2n, n?N
则（p, q）=(2m,2n)=2(m, n)≥2与（p, q）=1矛盾
1/2
所以假设不成立，原结论正确，2不是有理数。
1/21/2
（2）假设是7有理数，则存在正整数m，n，使得7=p/q,且（m, n）=1
222
平方得：m=2n, 即7|m
将m表示成n个素数pi的乘积，m= p1 p2 p3 ……pn ， pi为素数。 因为7为素数，假设7 !| m，则7 !∈｛p1 ，p2，p3 ，……pn｝
2222 2
所以m= p1 p2 p3 ……pn=( p1 p2 p3 ……pn)( p1 p2 p3 ……pn)
22
所以7 !| m，与7|m矛盾，故7|m, m=7k 同理可知：7|n, n=7 k0
所以(m, n)=(7k,7 k0)=7(k, k0)≥7 与已知矛盾
1/2
故原结论正确，7不是有理数。
1/2
（3）同理可证17不是有理数。
41．证明：假设log210是有理数，则存在正整数p, q,使得log210=p/q,且（p, q）=1 又log210=ln10/ln2=p/q
qpqp
Ln10=ln2 10=2
qpqp-q
(2*5)=2 5=2
所以只有当q=p=0是成立，所以假设不成立 故原结论正确，log210是无理数。 同理可证log37，log1521都是无理数。
32
50．（1）解：因为8=2, 60=2*3*5
3
所以[8,60]=2*3*5=120
11111001111111000000010001000
51．（4）解：(4779101,4183101)= 41477983101=101
1111100111111100011111111111001
[4779101,4183101]= 41477983101
第二章 同余
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不能实现。
22
2．证明：当m>2时，因为(m-1)=m-2m+1=m(m-2)+1
2
所以(m-1)≡1(mod m)
2222
即1与(m-1)在同一个剩余类中，故0,1,…,(m-1)一定不是模m的完全剩余系。
123
6．解：2≡2(mod7), 2≡4(mod7), 2≡1(mod7) 又20080509=6693503*3
3
所以2=(2)6693503≡1(mod7)
20080509
故2是星期六。 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)
2222
8．证明：如果a≡b(mod p) 则a= b+kp , k?Z
22
即kp=a-b=(a+b)(a-b) 所以p|(a+b)(a-b)
又p为素数，根据1.4定理2知p|a+b或p|a-b 得证。
2222
9．证明：如果a≡b(mod n) 则a= b+kn , k?Z
22
即kn=a-b=(a+b)(a-b) 所以n|(a+b)(a-b)
22
由n=pq知kpq=a-b=(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）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)
200805093
4
所以等式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) 所以(m)
?a?-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) 又(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
≡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 故原同余式有解
5
a7
≡a(mod9) 即
