2024年3月17日发(作者：象雨文)
信息安全数学基础习题答案
第一章 整数的可除性
1．证明：因为2|n 所以n=2k , k
Z
5|n 所以5|2k ， 又（5，2）=1，所以5|k 即k=5 k
1
，k
1
Z
7|n 所以7|2*5 k
1
,又（7，10）=1，所以7| k
1
即k
1
=7 k
2
，k
2
Z
所以n=2*5*7 k
2
即n=70 k
2
, k
2
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 k
0
+1， k
0
Z
22
（2 k
0
+1）＝4 k
0
+4 k
0
+1=4 k
0
(k
0
+1)+1
由于k
0
与k
0
+1为两连续整数，必有一个为偶数，所以k
0
(k
0
+1)=2k
2
所以（2 k
0
+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．证明：p
1
p
2
p
3
|n， 则n= p
1
p
2
p
3
k，k
N
3 31/3
又p
1
≤ p
2
≤p
3
，所以n= p
1
p
2
p
3
k≥p
1
即p
1
≤n
2
p
1
为素数 则p
1
≥2，又p
1
≤ p
2
≤p
3
，所以n= p
1
p
2
p
3
k≥2 p
2
p
3
≥2p
2
1/2
即p
2
≤(n/2) 得证。
1/2
11．解：小于等于500的所有素数为2，3，5，7，11，13，17，19，依次删除这些素数的
倍数可得所求素数：
12．证明：反证法
假设3k+1没有相同形式的素因数，则它一定只能表示成若干形如3k-1的素数相
乘。 (3 k
1
+1)(3 k
2
+1)=[( 3 k
1
+1) k
2
+ k
1
]*3+1 显然若干个3k+1的素数相乘，得
到的还是3k+1的形式，不能得出3k-1的数，因此假设不成立，结论得证。
同理可证其他。
13．证明：反证法
假设形如4k+3的素数只有有限个，记为p
1
, p
2
,…, p
n
因为4k+3=4k`-1=4k-1 构造N=4*p
1
*p
2
*…*p
n
-1≥3*p
1
*p
2
*…*p
n
所以N＞p
i
(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)
2024年3月17日发(作者：象雨文)
信息安全数学基础习题答案
第一章 整数的可除性
1．证明：因为2|n 所以n=2k , k
Z
5|n 所以5|2k ， 又（5，2）=1，所以5|k 即k=5 k
1
，k
1
Z
7|n 所以7|2*5 k
1
,又（7，10）=1，所以7| k
1
即k
1
=7 k
2
，k
2
Z
所以n=2*5*7 k
2
即n=70 k
2
, k
2
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 k
0
+1， k
0
Z
22
（2 k
0
+1）＝4 k
0
+4 k
0
+1=4 k
0
(k
0
+1)+1
由于k
0
与k
0
+1为两连续整数，必有一个为偶数，所以k
0
(k
0
+1)=2k
2
所以（2 k
0
+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．证明：p
1
p
2
p
3
|n， 则n= p
1
p
2
p
3
k，k
N
3 31/3
又p
1
≤ p
2
≤p
3
，所以n= p
1
p
2
p
3
k≥p
1
即p
1
≤n
2
p
1
为素数 则p
1
≥2，又p
1
≤ p
2
≤p
3
，所以n= p
1
p
2
p
3
k≥2 p
2
p
3
≥2p
2
1/2
即p
2
≤(n/2) 得证。
1/2
11．解：小于等于500的所有素数为2，3，5，7，11，13，17，19，依次删除这些素数的
倍数可得所求素数：
12．证明：反证法
假设3k+1没有相同形式的素因数，则它一定只能表示成若干形如3k-1的素数相
乘。 (3 k
1
+1)(3 k
2
+1)=[( 3 k
1
+1) k
2
+ k
1
]*3+1 显然若干个3k+1的素数相乘，得
到的还是3k+1的形式，不能得出3k-1的数，因此假设不成立，结论得证。
同理可证其他。
13．证明：反证法
假设形如4k+3的素数只有有限个，记为p
1
, p
2
,…, p
n
因为4k+3=4k`-1=4k-1 构造N=4*p
1
*p
2
*…*p
n
-1≥3*p
1
*p
2
*…*p
n
所以N＞p
i
(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)