2024年3月17日发(作者：束冬易)
第一章 整除理论
整除性理论是初等数论的基础。本章要介绍带余数除法，辗转相
除法，最大公约数，最小公倍数，算术基本定理以及它们的一些应用。
第一节 数的整除性
定义1 设a，b是整数，b 0，如果存在整数c，使得
a = bc
成立，则称a被b整除，a是b的倍数，b是a的约数（因数或除数），
并且使用记号ba；如果不存在整数c使得a = bc成立，则称a不被b
整除，记为b
|
a。
显然每个非零整数a都有约数 1，a，称这四个数为a的平凡约
数，a的另外的约数称为非平凡约数。
被2整除的整数称为偶数，不被2整除的整数称为奇数。
定理1 下面的结论成立：
(ⅰ) ab ab；
(ⅱ) ab，bc ac；
(ⅲ) ba
i
，i = 1, 2, , k ba
1
x
1
a
2
x
2
a
k
x
k
，此处x（
i
i =
1, 2, , k）是任意的整数；
(ⅳ) ba bcac，此处c是任意的非零整数；
(ⅴ) ba，a 0 |b| |a|；ba且|a| < |b| a = 0。
证明 留作习题。
定义2 若整数a 0，1，并且只有约数 1和 a，则称a是素
数（或质数）；否则称a为合数。
以后在本书中若无特别说明，素数总是指正素数。
定理2 任何大于1的整数a都至少有一个素约数。
1
证明 若a是素数，则定理是显然的。
若a不是素数，那么它有两个以上的正的非平凡约数，设它们是
d
1
, d
2
, , d
k
。不妨设d
1
是其中最小的。若d
1
不是素数，则存在e
1
> 1，
e
2
> 1，使得d
1
= e
1
e
2
，因此，e
1
和e
2
也是a的正的非平凡约数。这与
d
1
的最小性矛盾。所以d
1
是素数。证毕。
推论 任何大于1的合数a必有一个不超过
a
的素约数。
证明 使用定理2中的记号，有a = d
1
d
2
，其中d
1
> 1是最小的素
约数，所以d
1
2
a。证毕。
例1 设r是正奇数，证明：对任意的正整数n，有
n 2
|
1
r
2
r
n
r
。
解 对于任意的正整数a，b以及正奇数k，有
a
k
b
k
= (a b)(a
k
1
a
k
2
b a
k
3
b
2
b
k
1
) = (a b)q，
其中q是整数。记s = 1
r
2
r
n
r
，则
2s = 2 (2
r
n
r
) (3
r
(n 1)
r
) (n
r
2
r
) = 2 (n 2)Q，
其中Q是整数。若n 2s，由上式知n 22，因为n 2 > 2，这是
不可能的，所以n 2
|
s。
例2 设A = { d
1
, d
2
, , d
k
}是n的所有约数的集合，则
B =
{
nnn
,,
,
}
d
1
d
2
d
k
也是n的所有约数的集合。
解 由以下三点理由可以证得结论：
(ⅰ) A和B的元素个数相同；
n
(ⅱ) 若d
i
A，即d
i
n，则
|
n，反之亦然；
d
i
nn
(ⅲ) 若d
i
d
j
，则。
d
i
d
j
例3 以d(n)表示n的正约数的个数，例如：d(1) = 1，d(2) = 2，
d(3) = 2，d(4) = 3，
。问：
d(1) d(2) d(1997)
2
是否为偶数？
n
，因此，n的正约数d与
d
nnn
是成对地出现的。只有当d =，即n = d
2
时，d和才是同一个数。
ddd
故当且仅当n是完全平方数时，d(n)是奇数。
因为44
2
< 1997 < 45
2
，所以在d(1), d(2), , d(1997)中恰有44个
解 对于n的每个约数d，都有n = d
奇数，故d(1) d(2) d(1997)是偶数。
例4 设凸2n边形M的顶点是A
1
, A
2
, , A
2n
，点O在M的内部，
用1, 2, , 2n将M的2n条边分别编号，又将OA
1
, OA
2
, , OA
2n
也同
样进行编号，若把这些编号作为相应的线段的长度，证明：无论怎么
编号，都不能使得三角形OA
1
A
2
, OA
2
A
3
, , OA
2n
A
1
的周长都相等。
解 假设这些三角形的周长都相等，记为s。则
2ns = 3(1 2 2n) = 3n(2n 1)，
即
2s = 3(2n 1)，
因此23(2n 1)，这是不可能的，这个矛盾说明这些三角形的周长不
可能全都相等。
例5 设整数k 1，证明：
(ⅰ) 若2
k
n < 2
k
1
，1 a n，a 2
k
，则2
k
|
a；
(ⅱ) 若3
k
2n
1 < 3
k
+ 1
，1 b n，2b
1 3
k
，则3
k
|
2b
1。
解 (ⅰ) 若2
k
|a
，
则存在整数q，使得a= q2
k
。显然q只可能是
0或1。此时a= 0或2
k
，这都是不可能的，所以2
k
|
a；
(ⅱ) 若 3
k
|2b-1，则存在整数q，使得2b-1= q3
k
，显然q只可能
是0，1, 或2。此时2b-1= 0，3
k
，或
23
，这都是不可能的，所以
3
k
|
2b
1。
例6 写出不超过100的所有的素数。
解 将不超过100的正整数排列如下：
1 2 3 4 5 6 7 8 9 10
3
k
11 12 13 14 15 16 17 18 19 20
21 22 23 24 25 26 27 28 29 30
31 32 33 34 35 36 37 38 39 40
41 42 43 44 45 46 47 48 49 50
51 52 53 54 55 56 57 58 59 60
61 62 63 64 65 66 67 68 69 70
71 72 73 74 75 76 77 78 79 80
81 82 83 84 85 86 87 88 89 90
91 92 93 94 95 96 97 98 99 100
按以下步骤进行：
(ⅰ) 删去1，剩下的后面的第一个数是2，2是素数；
(ⅱ) 删去2后面的被2整除的数，剩下的2后面的第一个数是3，
3是素数；
(ⅲ) 再删去3后面的被3整除的数，剩下的3后面的第一个数
是5，5是素数；
(ⅳ) 再删去5后面的被5整除的数，剩下的5后面的第一个数
是7，7是素数；
照以上步骤可以依次得到素数2, 3, 5, 7, 11, 。
由定理2推论可知，不超过100的合数必有一个不超过10的素约
数，因此在删去7后面被7整除的数以后，就得到了不超过100的全
部素数。
在例6中所使用的寻找素数的方法，称为Eratosthenes筛法。它可
以用来求出不超过任何固定整数的所有素数。在理论上这是可行的；
但在实际应用中，这种列出素数的方法需要大量的计算时间，是不可
取的。
例7 证明：存在无穷多个正整数a，使得
n
4
a（n = 1, 2, 3, ）
都是合数。
解 取a = 4k
4
，对于任意的nN，有
n
4
4k
4
= (n
2
2k
2
)
2
4n
2
k
2
= (n
2
2k
2
2nk)(n
2
2k
2
2nk)。
因为
4
n
2
2k
2
2nk = (n k)
2
k
2
k
2
，
所以，对于任意的k = 2, 3, 以及任意的nN，n
4
a是合数。
例8 设a
1
, a
2
, , a
n
是整数，且
a
1
a
2
a
n
= 0，a
1
a
2
a
n
= n，
则4n。
解 如果2
|
n，则n, a
1
, a
2
, , a
n
都是奇数。于是a
1
a
2
a
n
是奇数个奇数之和，不可能等于零，这与题设矛盾，所以2n，即在
a
1
, a
2
, , a
n
中至少有一个偶数。如果只有一个偶数，不妨设为a
1
，那
么2
。此时有等式
|
a
i
（2 i n）
a
2
a
n
= a
1
，
在上式中，左端是(n 1)个奇数之和，右端是偶数，这是不可能的，
因此，在a
1
, a
2
, , a
n
中至少有两个偶数，即4n。
例9 若n是奇数，则8n
2
1。
解 设n = 2k 1，则
n
2
1= (2k 1)
2
1 = 4k(k 1)。
在k和k 1中有一个是偶数，所以8n
2
1。
例9的结论虽然简单，却是很有用的。例如，使用例3中的记号，
我们可以提出下面的问题：
问题 d(1)
2
d(2)
2
d(1997)
2
被4除的余数是多少？
例10 证明：方程
a
1
2
a
2
2
a
3
2
= 1999 (1)
无整数解。
解 若a
1
，a
2
，a
3
都是奇数，则存在整数A
1
，A
2
，A
3
，使得
a
1
2
= 8A
1
1，a
2
2
= 8A
2
1，a
3
2
= 8A
3
1，
于是
a
1
2
a
2
2
a
3
2
= 8(A
1
A
2
A
3
) 3。
由于1999被8除的余数是7，所以a
1
，a
2
，a
3
不可能都是奇数。
由式(1)，a
1
，a
2
，a
3
中只能有一个奇数，设a
1
为奇数，a
2
，a
3
为
偶数，则存在整数A
1
，A
2
，A
3
，使得
a
1
2
= 8A
1
1，a
2
2
= 8A
2
r，a
3
2
= 8A
3
s，
5
于是
a
1
2
a
2
2
a
3
2
= 8(A
1
A
2
A
3
) 1 r s，
其中r和s是整数，而且只能取值0或4。这样a
1
2
a
2
2
a
3
2
被8除的
余数只可能是1或5，但1999被8除的余数是7，所以这样的a
1
，a
2
，
a
3
也不能使式(2)成立。
综上证得所需要的结论。
习 题 一
1. 证明定理1。
2. 证明：若m pmn pq，则m pmq np。
3. 证明：任意给定的连续39个自然数，其中至少存在一个自然
数，使得这个自然数的数字和能被11整除。
4. 设p是n的最小素约数，n = pn
1
，n
1
> 1，证明：若p >
3
n
，
则n
1
是素数。
5. 证明：存在无穷多个自然数n，使得n不能表示为
a
2
p（a > 0是整数，p为素数）
的形式。
第二节 带余数除法
在本节中，我们要介绍带余数除法及其简单应用。
定理1(带余数除法) 设a与b是两个整数，b 0，则存在唯一的
两个整数q和r，使得
a = bq r，0 r < |b|。 (1)
|
a，考虑证明 存在性 若ba，a = bq，qZ，可取r = 0。若b
集合
A = { a kb；kZ },
其中Z表示所有整数的集合，以后，仍使用此记号，并以N表示所有
正整数的集合。
在集合A中有无限多个正整数，设最小的正整数是r = a k
0
b，则
6
必有
0 < r < |b|， (2)
否则就有r |b|。因为b
|
a，所以r |b|。于是r > |b|，即a k
0
b > |b|，
a k
0
b
|b| > 0，这样，在集合A中，又有正整数a k
0
b
|b| < r，这
与r的最小性矛盾。所以式(2)必定成立。取q =
k
0
知式(1)成立。存
在性得证。
唯一性 假设有两对整数q
，r
与q
，r
都使得式(1)成立，即
a = q
b r
= q
b r
，0 r
, r
< |b|，
则
(q
q
)b = r
r
，|r
r
| < |b|， (3)
因此r
r
= 0，r
= r
，再由式(3)得出q
= q
，唯一性得证。证毕。
定义1 称式(1)中的q是a被b除的商，r是a被b除的余数。
由定理1可知，对于给定的整数b，可以按照被b除的余数将所
有的整数分成b类。在同一类中的数被b除的余数相同。这就使得许
多关于全体整数的问题可以归化为对有限个整数类的研究。
以后在本书中，除特别声明外，在谈到带余数除法时总是假定b
是正整数。
例1 设a，b，x，y是整数，k和m是正整数，并且
a = a
1
m r
1
，0 r
1
< m，
b = b
1
m r
2
，0 r
2
< m，
则ax by和ab被m除的余数分别与r
1
x r
2
y和r
1
r
2
被m除的余数相
同。特别地，a
k
与r
1
k
被m除的余数相同。
解 由
ax by = (a
1
m r
1
)x (b
1
m r
2
)y = (a
1
x b
1
y)m r
1
x r
2
y
可知，若r
1
x r
2
y被m除的余数是r，即
r
1
x r
2
y = qm r，0 r < m，
则
ax by = (a
1
x b
1
y q)m r，0 r < m，
即ax by被m除的余数也是r。
同样方法可以证明其余结论。
例2 设a
1
, a
2
, , a
n
为不全为零的整数，以y
0
表示集合
A = { y；y = a
1
x
1
a
n
x
n
，x
i
Z，1 i n }
7
中的最小正数，则对于任何yA，y
0
y；特别地，y
0
a
i
，1 i n。
解 设y
0
= a
1
x
1
a
n
x
n
，对任意的y = a
1
x
1
a
n
x
n
A，由
定理1，存在q, r
0
Z，使得
y = qy
0
r
0
，0 r
0
< y
0
。
因此
r
0
= y
qy
0
= a
1
(x
1
qx
1
) a
n
(x
n
qx
n
)A。
如果r
0
0，那么，因为0 < r
0
< y
0
，所以r
0
是A中比y
0
还小的正
数，这与y
0
的定义矛盾。所以r
0
= 0，即y
0
y。
显然a
i
A（1 i n），所以y
0
整除每个a
i
（1 i n）。
例3 任意给出的五个整数中，必有三个数之和被3整除。
解 设这五个数是a
i
，i = 1, 2, 3, 4, 5，记
a
i
= 3q
i
r
i
，0 r
i
< 3，i = 1, 2, 3, 4, 5。
分别考虑以下两种情形：
(ⅰ) 若在r
1
, r
2
, , r
5
中数0，1，2都出现，不妨设r
1
= 0，r
2
= 1，
r
3
= 2，此时
a
1
a
2
a
3
= 3(q
1
q
2
q
3
) 3
可以被3整除；
(ⅱ) 若在r
1
, r
2
, , r
5
中数0，1，2至少有一个不出现，这样至
少有三个r
i
要取相同的值，不妨设r
1
= r
2
= r
3
= r（r = 0，1或2），此
时
a
1
a
2
a
3
= 3(q
1
q
2
q
3
) 3r
可以被3整除。
例4 设a
0
, a
1
, , a
n
Z，f(x) = a
n
x
n
a
1
x a
0
，已知f(0)与
f(1)都不是3的倍数，证明：若方程f(x) = 0有整数解，则
3f(
1) = a
0
a
1
a
2
(
1)
n
a
n
。
解 对任何整数x，都有
x = 3q r，r = 0，1或2，qZ。
(ⅰ) 若r = 0，即x = 3q，qZ，则
f(x) = f(3q) = a
n
(3q)
n
a
1
(3q) a
0
= 3Q
1
a
0
= 3Q
1
f(0)，
其中Q
1
Z，由于f(0)不是3的倍数，所以f(x) 0；
(ⅱ) 若r = 1，即x = 3q 1，qZ，则
8
f(x) = f(3q 1) = a
n
(3q 1)
n
a
1
(3q 1) a
0
= 3Q
2
a
n
a
1
a
0
= 3Q
2
f(1)，
其中Q
2
Z。由于f(1)不是3的倍数，所以f(x) 0。
因此若f(x) = 0有整数解x，则必是x = 3q 2 = 3q
1，q
Z，于
是
0 = f(x) = f(3q
1) = a
n
(3q
1)
n
a
1
(3q
1) a
0
= 3Q
3
a
0
a
1
a
2
(
1)
n
a
n
= 3Q
3
f(
1)，
其中Q
3
Z。所以3f(
1) = a
0
a
1
a
2
(
1)
n
a
n
。
例5 证明：对于任意的整数n，f(n) = 3n
5
5n
3
7n被15整除。
解 对于任意的正整数n，记
n = 15q r，0 r < 15。
由例1，
n
2
= 15Q
1
r
1
，n
4
= 15Q
2
r
2
，
其中r
1
与r
2
分别是r
2
与r
4
被15除的余数。
以R表示3n
4
5n
2
7被15除的余数，则R就是3r
2
5r
1
7被
15除的余数，而且f(n)被15除的余数就是rR被15除的余数，记为R
。
当r = 0时，显然R
= 0，即153n
5
5n
3
7n。
对于r = 1, 2, 3, , 14的情形，通过计算列出下表：
r = 1, 14 2, 13 3, 12 4, 11 5, 10 6, 9 7, 8
r
1
= 1 4 9 1 10 6 4
r
2
= 1 1 6 1 10 6 1
R = 0 0 10 0 12 10 0
R= 0 0 0 0 0 0 0
这证明了结论。
例6 设n是奇数，则16n
4
4n
2
11。
解 我们有
n
4
4n
2
11 = (n
2
1)(n
2
5) 16。
由第一节例题9，有8n
2
1，由此及2n
2
5得到16(n
2
1)(n
2
5)。
例7 证明：若a被9除的余数是3，4，5或6，则方程x
3
y
3
=
9
a没有整数解。
解 对任意的整数x，y，记
x = 3q
1
r
1
，y = 3q
2
r
2
，0 r
1
, r
2
< 3。
则存在Q
1
, R
1
, Q
2
, R
2
Z，使得
x
3
= 9Q
1
R
1
，y
3
= 9Q
2
R
2
，
其中R
1
和R
2
被9除的余数分别与r
1
3
和r
2
3
被9除的余数相同，即
R
1
= 0，1或8，R
2
= 0，1或8。 (4)
因此
x
3
y
3
= 9(Q
1
Q
2
) R
1
R
2
。
又由式(4)可知，R
1
R
2
被9除的余数只可能是0，1，2，7或8，所以，
x
3
y
3
不可能等于a
。
习 题 二
1. 证明：12n
4
2n
3
11n
2
10n，nZ。
2. 设3a
2
b
2
，证明：3a且3b。
3. 设n，k是正整数，证明：n
k
与n
k
+ 4
的个位数字相同。
4. 证明：对于任何整数n，m，等式n
2
(n 1)
2
= m
2
2不可能
成立。
5. 设a是自然数，问a
4
3a
2
9是素数还是合数？
6. 证明：对于任意给定的n个整数，必可以从中找出若干个作
和，使得这个和能被n整除。
第三节 最大公约数
定义1 整数a
1
, a
2
, , a
k
的公共约数称为a
1
, a
2
, , a
k
的公约数。
不全为零的整数a
1
, a
2
, , a
k
的公约数中最大的一个叫做a
1
, a
2
, , a
k
的最大公约数（或最大公因数），记为(a
1
, a
2
, , a
k
)。
由于每个非零整数的约数的个数是有限的，所以最大公约数是存
在的，并且是正整数。
10
如果(a
1
, a
2
, , a
k
) = 1，则称a
1
, a
2
, , a
k
是互素的（或互质的）；
如果
(a
i
, a
j
) = 1，1 i, j k，i j，
则称a
1
, a
2
, , a
k
是两两互素的（或两两互质的）。
显然，a
1
, a
2
, , a
k
两两互素可以推出(a
1
, a
2
, , a
k
) = 1，反之则不
然，例如(2, 6, 15) = 1，但(2, 6) = 2。
定理1 下面的等式成立：
(ⅰ) (a
1
, a
2
, , a
k
) = (|a
1
|, |a
2
|, , |a
k
|)；
(ⅱ) (a, 1) = 1，(a, 0) = |a|，(a, a) = |a|；
(ⅲ) (a, b) = (b, a)；
(ⅳ) 若p是素数，a是整数，则(p, a) = 1或pa；
(ⅴ) 若a = bq r，则(a, b) = (b, r)。
证明 (ⅰ)(ⅳ)留作习题。
(ⅴ) 由第一节定理1可知，如果da，db，则有dr = a bq，
反之，若db，dr，则da = bq r。因此a与b的全体公约数的集
合就是b与r的全体公约数的集合，这两个集合中的最大正数当然相
等，即(a, b) = (b, r)。证毕。
由定理1可知，在讨论(a
1
, a
2
, , a
n
)时，不妨假设a
1
, a
2
, , a
n
是
正整数，以后我们就维持这一假设。
定理2 设a
1
, a
2
, , a
k
Z，记
A = { y；y =
a
i
x
i
，x
i
Z， i k }。
i1
k
如果y
0
是集合A中最小的正数，则y
0
= (a
1
, a
2
, , a
k
)。
证明 设d是a
1
, a
2
, , a
k
的一个公约数，则dy
0
，所以d y
0
。
另一方面，由第二节例2知，y
0
也是a
1
, a
2
, , a
k
的公约数。因此y
0
是a
1
, a
2
, , a
k
的公约数中的最大者，即y
0
= ( a
1
, a
2
, , a
k
)。证毕。
推论1 设d是a
1
, a
2
, , a
k
的一个公约数，则d(a
1
, a
2
, , a
k
)。
这个推论对最大公约数的性质做了更深的刻划：最大公约数不但
是公约数中的最大的，而且是所有公约数的倍数。
11
推论2 (ma
1
, ma
2
, , ma
k
) = |m|(a
1
, a
2
, , a
k
)。
推论3 记
= (a
1
, a
2
, , a
k
)，则
(
特别地,
a
a
1
a
2
,,
,
k
)
= 1，
(
ab
,
)
= 1。
(a,b)(a,b)
定理3 (a
1
, a
2
, , a
k
) = 1的充要条件是存在整数x
1
, x
2
, , x
k
，使
得
a
1
x
1
a
2
x
2
a
k
x
k
= 1。 (1)
证明 必要性 由定理2得到。
充分性 若式(1)成立，如果 (a
1
, a
2
, , a
k
) = d > 1，那么由da
i
（1 i
k）推出da
1
x
1
a
2
x
2
a
k
x
k
= 1，这是不可能的。所以有(a
1
, a
2
, ,
a
k
) = 1。证毕。
定理4 对于任意的整数a，b，c，下面的结论成立：
(ⅰ) 由bac及(a, b) = 1可以推出bc；
(ⅱ) 由bc，ac及(a, b) = 1可以推出abc。
证明 (ⅰ) 若(a, b) = 1，由定理2，存在整数x与y，使得
ax by = 1。
因此
acx bcy = c。 (2)
由上式及bac得到bc。结论(ⅰ)得证；
(ⅱ) 若(a, b) = 1，则存在整数x，y使得式(2)成立。由bc与ac
得到abac，abbc，再由式(2)得到abc。结论(ⅱ)得证。证毕。
推论1 若p是素数，则下述结论成立：
(ⅰ) pab pa或pb；
(ⅱ) pa
2
pa。
证明 留作习题。
推论2 若 (a, b) = 1，则(a, bc) = (a, c)。
证明 设d是a与bc的一个公约数，则da，dbc，由式（2）
得到，d|c, 即d是a与c的公约数。另一方面，若d是a与c的公约
数，则它也是a与bc的公约数。因此，a与c的公约数的集合，就是
12
a与bc的公约数的集合，所以(a, bc) = (a, c)。证毕。
推论3 若 (a, b
i
) = 1，1 i n，则(a, b
1
b
2
b
n
) = 1。
证明 留作习题。
定理5 对于任意的n个整数a
1
, a
2
, , a
n
，记
(a
1
, a
2
) = d
2
，(d
2
, a
3
) = d
3
，，(d
n 2
, a
n 1
) = d
n 1
，(d
n 1
, a
n
) = d
n
，
则
d
n
= (a
1
, a
2
, , a
n
)。
证明 由定理2的推论，我们有
d
n
= (d
n 1
, a
n
) d
n
a
n
，d
n
d
n 1
，
d
n 1
= (d
n 2
, a
n 1
) d
n 1
a
n 1
，d
n 1
d
n 2
，
d
n
a
n
，d
n
a
n 1
，d
n
d
n 2
，
d
n 2
= (d
n 3
, a
n 2
) d
n 2
a
n 2
，d
n 2
d
n 3
d
n
a
n
，d
n
a
n 1
，d
n
a
n 2
，d
n
d
n 3
，
d
2
= (a
1
, a
2
) d
n
a
n
，d
n
a
n 1
，，d
n
a
2
，d
n
a
1
，
即d
n
是a
1
, a
2
, , a
n
的一个公约数。
另一方面，对于a
1
, a
2
, , a
n
的任何公约数d，由定理2的推论及
d
2
, , d
n
的定义，依次得出
da
1
，da
2
dd
2
，
dd
2
，da
3
dd
3
，
dd
n 1
，da
n
dd
n
，
因此d
n
是a
1
, a
2
, , a
n
的公约数中的最大者，即d
n
= (a
1
, a
2
, , a
n
)。证
毕。
例1 证明：若n是正整数，则
21n4
是既约分数。
14n3
解 由定理1得到
(21n 4, 14n 3) = (7n 1, 14n 3) = (7n 1, 1) = 1。
注：一般地，若(x, y) = 1，那么，对于任意的整数a，b，有
13
(x, y) = (x ay, y) = (x ay, y b(x ay)) = (x ay, (ab 1)y bx)，
xay
因此，是既约分数。
(ab1)ybx
例2 证明：121
|
n
2
2n 12，nZ。
解 由于121 = 11
2
，n
2
2n 12 = (n 1)
2
11，所以，若
11
2
(n 1)
2
11， (3)
则11(n 1)
2
，因此，由定理4的推论1得到
11n 1，11
2
(n 1)
2
。
再由式(3)得到
11
2
11，
这是不可能的。所以式(3)不能成立。
注：这个例题的一般形式是：
设p是素数，a，b是整数，则
p
k
|
(an b)
k
p
k
1
c，
其中c是不被p整除的任意整数，k是任意的大于1的整数。
例3 设a，b是整数，且
9a
2
ab b
2
， (4)
则3(a, b)。
解 由式(4)得到
9(a b)
2
3ab 3(a b)
2
3ab
3(a b)
2
3a b (5)
9(a b)
2
。
再由式(4)得到
93ab 3ab。
因此，由定理4的推论1，得到
3a或3b。
若3a，由式(5)得到3b；若3b，由(5)式也得到3a。因此，
总有3a且3b。
由定理2的推论推出3(a, b)。
|
2
a
1。 例4 设a和b是正整数，b > 2，则2
b
1
解 (ⅰ) 若a < b，且
2
b
12
a
1。 (6)
14
成立，则
2
b
1 2
a
1 2
b
2
a
2 2
a
(2
b
a
1) 2，
于是a = 1，b a = 1，即b = 2，这是不可能的，所以式(6)不成立。
(ⅱ) 若a = b，且式(6)成立，则由式(6)得到
2
a
1(2
a
1) 2 2
a
12 2
a
1 2 2
a
3，
于是b = a = 1，这是不可能的，所以式(6)不成立。
(ⅲ) 若a > b，记a = kb r，0 r < b，此时
2
kb
1 = (2
b
1)(2
(
k
1)
b
2
(
k
2)
b
1) = (2
b
1)Q，
其中Q是整数。所以
2
a
1 = 2
kb + r
1 = 2
r
(2
kb
1 1) 1
rbbr
= 2((2 1)Q 1) 1 = (2 1)Q (2 1)，
其中Q是整数。因此
2
b
12
a
1 2
b
12
r
1，
在(ⅰ)中已经证明这是不可能的，所以式(6)不能成立。
综上证得2
b
1
|
2
a
1。
习 题 三
1. 证明定理1中的结论(ⅰ)—(ⅳ)。
2. 证明定理2的推论1, 推论2和推论3。
3. 证明定理4的推论1和推论3。
4. 设x，yZ，172x 3y，证明：179x 5y。
5. 设a，b，cN，c无平方因子，a
2
b
2
c，证明：ab。
32n1
6. 设n是正整数，求
C
1
2n
,C
2n
,
,C
2n
的最大公约数。
第四节 最小公倍数
定义1 整数a
1
, a
2
, , a
k
的公共倍数称为a
1
, a
2
, , a
k
的公倍数。
a
1
, a
2
, , a
k
的正公倍数中的最小的一个叫做a
1
, a
2
, , a
k
的最小公倍
15
数，记为[a
1
, a
2
, , a
k
]。
定理1 下面的等式成立：
(ⅰ) [a, 1] = |a|，[a, a] = |a|；
(ⅱ) [a, b] = [b, a]；
(ⅲ) [a
1
, a
2
, , a
k
] = [|a
1
|, |a
2
| , |a
k
|]；
(ⅳ) 若ab，则[a, b] = |b|。
证明 留作习题。
由定理1中的结论(ⅲ)可知，在讨论a
1
, a
2
, , a
k
的最小公倍数时，
不妨假定它们都是正整数。在本节中总是维持这一假定。
最小公倍数和最大公约数之间有一个很重要的关系，即下面的定
理。
定理2 对任意的正整数a，b，有
ab
[a, b] =。
(a,b)
证明 设m是a和b的一个公倍数，那么存在整数k
1
，k
2
，使得
m = ak
1
，m = bk
2
，因此
ak
1
= bk
2
。 (1)
于是
ab
k
1
k
2
。
(a,b)(a,b)
ab
由于
(
,
)
= 1，所以由第三节定理4得到
(a,b)(a,b)
b
|
k
1
，即k
1
b
t
，
(a,b)(a,b)
其中t是某个整数。将上式代入式(1)得到
ab
m =t
。 (2)
(a,b)
另一方面，对于任意的整数t，由式(2)所确定的m显然是a与b
的公倍数，因此a与b的公倍数必是式(2)中的形式，其中t是整数。
当t = 1时，得到最小公倍数
16
[a, b] =
ab
。
(a,b)
证毕。
推论1 两个整数的任何公倍数可以被它们的最小公倍数整除。
证明 由式(2)可得证。证毕。
这个推论说明：两个整数的最小公倍数不但是最小的正倍数，而
且是另外的公倍数的约数。
推论2 设m，a，b是正整数，则[ma, mb] = m[a, b]。
证明 由定理2及第三节定理2的推论得到
m
2
abm
2
abmab
[ma, mb] == m[a, b]。
(ma,mb)m(a,b)(a,b)
证毕。
定理3 对于任意的n个整数a
1
, a
2
, , a
n
，记
[a
1
, a
2
] = m
2
，[m
2
, a
3
] = m
3
，，[m
n2
, a
n1
] = m
n1
，[m
n1
, a
n
] = m
n
，
则
[a
1
, a
2
, , a
n
] = m
n
。
证明 我们有
m
n
= [m
n1
, a
n
] m
n1
m
n
，a
n
m
n
，
m
n1
= [m
n2
, a
n1
] m
n2
m
n1
m
n
，a
n
m
n
，a
n1
m
n1
m
n
，
m
n2
= [m
n3
, a
n2
] m
n3
m
n2
m
n
，a
n
m
n
，a
n1
m
n
，a
n2
m
n
，
m
2
= [a
1
, a
2
] a
n
m
n
，，a
2
m
n
，a
1
m
n
，
即m
n
是a
1
, a
2
, , a
n
的一个公倍数。
另一方面，对于a
1
, a
2
, , a
n
的任何公倍数m，由定理2的推论及
m
2
, , m
n
的定义，得
m
2
m，m
3
m，，m
n
m。
即m
n
是a
1
, a
2
, , a
n
最小的正的公倍数。证毕。
推论 若m是整数a
1
, a
2
, , a
n
的公倍数，则[a
1
, a
2
, , a
n
]m
。
证明 留作习题。
17
定理4 整数a
1
, a
2
, , a
n
两两互素，即
(a
i
, a
j
) = 1，1 i, j n，i j
的充要条件是
[a
1
, a
2
, , a
n
] = a
1
a
2
a
n
。 (3)
证明 必要性 因为(a
1
, a
2
) = 1，由定理2得到
aa
[a
1
, a
2
] =
12
= a
1
a
2
。
(a
1
,a
2
)
由(a
1
, a
3
) = (a
2
, a
3
) = 1及第三节定理4推论3得到
(a
1
a
2
, a
3
) = 1，
由此及定理3得到
[a
1
, a
2
, a
3
] = [[a
1
, a
2
], a
3
] = [a
1
a
2
, a
3
] = a
1
a
2
a
3
。
如此继续下去，就得到式(3)。
充分性 用归纳法证明。当n = 2时，式(3)成为[a
1
, a
2
] = a
1
a
2
。由
定理2
aa
a
1
a
2
= [a
1
, a
2
] =
12
(a
1
, a
2
) = 1，
(a
1
,a
2
)
即当n = 2时，充分性成立。
假设充分性当n = k时成立，即
[a
1
, a
2
, , a
k
] = a
1
a
2
a
k
(a
i
, a
j
) = 1，1 i, j k，i j。
对于整数a
1
, a
2
, , a
k
, a
k + 1
，使用定理3中的记号，由定理3可知
[a
1
, a
2
, , a
k
, a
k + 1
] = [m
k
, a
k + 1
]。 (4)
其中m
k
= [a
1
, a
2
, , a
k
]。因此，如果
[a
1
, a
2
, , a
k
, a
k + 1
] = a
1
a
2
a
k
a
k + 1
，
那么，由此及式(4)得到
[a
1
, a
2
, , a
k
, a
k + 1
] = [m
k
, a
k + 1
] =
即
m
k
= a
1
a
2
a
k
，
(m
k
,a
k1
)
m
k
a
k1
= a
1
a
2
a
k
a
k + 1
，
(m
k
,a
k1
)
18
显然m
k
a
1
a
2
a
k
，(m
k
, a
k + 1
) 1。所以若使上式成立，必是
(m
k
, a
k + 1
) = 1， (5)
并且
m
k
= a
1
a
2
a
k
。 (6)
由式(6)与式(5)推出
(a
i
, a
k + 1
) = 1，1 i k； (7)
由式(6)及归纳假设推出
(a
i
, a
j
) = 1，1 i, j k，i j
。 (8)
综合式(7)与式(8)，可知当n = k 1时，充分性成立。由归纳法证明了
充分性。证毕。
定理4有许多应用。例如，如果m
1
, m
2
, , m
k
是两两互素的整数，
那么，要证明m = m
1
m
2
m
k
整除某个整数Q，只需证明对于每个i，1
i k，都有m
i
Q。这一点在实际计算中是很有用的。对于函数f(x)，
要验证命题“mf(n)，nZ”是否成立，可以用第二节例5中的方法，
验证“mf(r)，r = 0, 1, , m 1”是否成立。这需要做m次除法。但
是，若分别验证“m
i
f(r
i
)，r
i
= 0, 1, , m
i
1，1 i k”是否成立，
则总共需要做m
1
m
2
m
k
次除法。后者的运算次数显然少于前
者。
例1 设a，b，c是正整数，证明：[a, b, c](ab, bc, ca) = abc
。
解 由定理3和定理2有
[a,b]c
[a, b, c] = [[a, b], c] =， (9)
([a,b],c)
由第三节定理5和定理2的推论，
(ab, bc, ca) = (ab, (bc, ca)) = (ab, c(a, b))
abc
)
(ab[a,b],abc)
ab([a,b],c)
。 (10) =
(
ab,
[a,b][a,b][a,b]
联合式(9)与式(10)得到所需结论。
例2 对于任意的整数a
1
, a
2
, , a
n
及整数k，1 k n，证明：
[a
1
, a
2
, , a
n
] = [[a
1
, , a
k
],[a
k + 1
, , a
n
]]
19
解 因为[a
1
, a
2
, , a
n
]是a
1
, , a
k
, a
k + 1
, , a
n
的公倍数，所以由
定理2推论，推出
[a
1
, , a
k
][a
1
, a
2
, , a
n
]，
[a
k + 1
, , a
n
][a
1
, a
2
, , a
n
]，
再由定理3推论知
[[a
1
, , a
k
], [a
k + 1
, , a
n
]][a
1
, a
2
, , a
n
]。 (11)
另一方面，对于任意的a
i
（1 i n），显然
a
i
[[a
1
, , a
k
], [a
k + 1
, , a
n
]]，
所以由定理3推论可知
[a
1
, a
2
, , a
n
][[a
1
, , a
k
], [a
k + 1
, , a
n
]]，
联合上式与式(11)得证。
例3 设a，b，c是正整数，证明：
[a, b, c][ab, bc, ca] = [a, b][b, c][c, a]。
解 由定理2推论2及例2，有
[a, b, c][ab, bc, ca] = [[a, b, c]ab, [a, b, c]bc, [a, b, c]ca]
= [[a
2
b, ab
2
, abc], [abc, b
2
c, bc
2
], [a
2
c, abc, ac
2
]]
= [a
2
b, ab
2
, abc, abc, b
2
c, bc
2
, a
2
c, abc, ac
2
]
= [abc, a
2
b, a
2
c, b
2
c, b
2
a, c
2
a, c
2
b]
以及
[a, b][b, c][c, a] = [[a, b]b, [a, b]c][c, a]
= [ab, b
2
, ac, bc][c, a]
= [ab[c, a], b
2
[c, a], ac[c, a], bc[c, a]]
= [abc, a
2
b, b
2
c, b
2
a, ac
2
, a
2
c, bc
2
, bca]
= [abc, a
2
b, a
2
c, b
2
c, b
2
a, c
2
a, c
2
b]，
由此得证。
习 题 四
1. 证明定理1。
2. 证明定理3的推论。
3. 设a，b是正整数，证明：(a b)[a, b] = a[b, a b]。
20
4. 求正整数a，b，使得a b = 120，(a, b) = 24，[a, b] = 144。
5. 设a，b，c是正整数，证明：
[a,b,c]
2
(a,b,c)
2
。
[a,b][b,c][c,a](a,b)(b,c)(c,a)
6. 设k是正奇数，证明：1 2 91
k
2
k
9
k
。
第五节 辗转相除法
本节要介绍一个计算最大公约数的算法——辗转相除法，又称
Euclid算法。它是数论中的一个重要方法，在其他数学分支中也有广
泛的应用。
定义1 下面的一组带余数除法，称为辗转相除法。
设a和b是整数，b 0，依次做带余数除法：
a = bq
1
r
1
，
0 < r
1
< |b|，
b = r
1
q
2
r
2
，
0 < r
2
< r
1
，
r
k 1
= r
k
q
k + 1
r
k + 1
，0 < r
k + 1
< r
k
， (1)
r
n 2
= r
n 1
q
n
r
n
， 0 < r
n
< r
n-1
，
r
n 1
= r
n
q
n + 1
。
由于b是固定的，而且
|b| > r
1
> r
2
> ，
所以式(1)中只包含有限个等式。
下面，我们要对式(1)所包含的等式的个数，即要做的带余数除法
的次数进行估计。
引理1 用下面的方式定义Fibonacci数列{F
n
}：
F
1
= F
2
= 1，F
n
= F
n 1
F
n 2
，n 3，
那么对于任意的整数n 3，有
F
n
>
n
2
， (2)
21
其中
=
15
。
2
证明 容易验证
2
=
1。
当n = 3时，由
F
3
= 2 >
15
=
2
可知式(2)成立。
假设式(2)对于所有的整数k n（n 3）成立，即
F
k
>
k
2
，k n，
则
F
n + 1
= F
n
F
n 1
>
n
2
n
3
=
n
3
(
1) =
n
3
2
=
n
1
，
即当k = n 1时式(2)也成立。由归纳法知式(2)对一切n 3成立。证
毕。
定理1(Lame) 设a, bN，a > b，使用在式(1)中的记号，则
n < 5log
10
b。
证明 在式(1)中，r
n
1，q
n + 1
2，q
i
1（1 i n），因此
r
n
1 = F
2
，
r
n 1
2r
n
2 = F
3
，
r
n 2
r
n 1
r
n
F
3
F
2
= F
4
，
b r
1
r
2
F
n + 1
F
n
= F
n + 2
，
由此及式(2)得
15
n
b
n
=
()
，
2
即
log
10
b nlog
10
151
n
，
25
这就是定理结论。证毕。
定理2 使用式(1)中的记号，记
P
0
= 1，P
1
= q
1
，P
k
= q
k
P
k 1
P
k 2
，k 2，
22
Q
0
= 0，Q
1
= 1，Q
k
= q
k
Q
k 1
Q
k 2
，k 2，
则
aQ
k
bP
k
= (1)
k
1
r
k
，k = 1, 2, , n 。 (3)
证明 当k = 1时，式(3)成立。
当k = 2时，有
Q
2
= q
2
Q
1
Q
0
= q
2
，P
2
= q
2
P
1
P
0
= q
2
q
1
1，
此时由式(1)得到
aQ
2
bP
2
= aq
2
b(q
2
q
1
1) = (a bq
1
)q
2
b = r
1
q
2
b = r
2
，
即式(3)成立。
假设对于k < m（1 m n）式(3)成立，由此假设及式(1)得到
aQ
m
bP
m
= a(q
m
Q
m 1
Q
m 2
) b(q
m
P
m 1
P
m 2
)
= (aQ
m 1
bP
m 1
)q
m
(aQ
m 2
bP
m 2
)
= (1)
m
2
r
m 1
q
m
(1)
m
3
r
m 2
= (1)
m
1
(r
m 2
r
m 1
q
m
) = (1)
m
1
r
m
，
即式(3)当k = m时也成立。定理由归纳法得证。证毕。
定理3 使用式(1)中的记号，有r
n
= (a, b)。
证明 由第三节定理1，从式(1)可见
r
n
= (r
n 1
, r
n
) = (r
n 2
, r
n 1
) = = (r
1
, r
2
) = (b, r
1
) = (a, b)。
证毕。
现在我们已经知道，利用辗转相除法可以求出整数x，y，使得
ax by = (a, b)
。 (4)
为此所需要的除法次数是O(log
10
b)。但是如果只需要计算(a, b)而不需
要求出使式(4)成立的整数x与y，则所需要的除法次数还可更少一些。
例1 设a和b是正整数，那么只使用被2除的除法运算和减法
运算就可以计算出(a, b)。
解 下面的四个基本事实给出了证明：
(ⅰ) 若ab，则(a, b) = a；
|
a
1
，b2
b
1
，2
|
b
1
，
1，则 (ⅱ) 若a = 2
a
1
，
2
(a, b) = 2
(2
a
1
, b
1
)；
|
a，b2
b
1
，2
|
b
1
，则(a, b) = (a, b
1
)； (ⅲ) 若
2
ab
(ⅳ) 若
2
|
a，2
|
b，则(a,b)
(||
,b
)
。
2
23
在实际计算过程中，若再灵活运用最大公约数的性质（例如第三
节定理4的推论），则可使得求最大公约数的过程更为简单。
例2 用辗转相除法求(125, 17)，以及x，y，使得
125x 17y = (125, 17)。
解 做辗转相除法：
125 = 717 6，q
1
= 7，r
1
= 6，
17 = 26 5， q
2
= 2，r
2
= 5，
6 = 15 1， q
3
= 1，r
3
= 1，
5 = 51， q
4
= 5。
由定理4，(125, 17) = r
3
= 1。
利用定理2计算（n = 3）
P
0
= 1，P
1
= 7，P
2
= 27 1 = 15，P
3
= 115 7 = 22，
Q
0
= 0，Q
1
= 1，Q
2
= 21 0 = 2，Q
3
= 12 1 = 3，
取x = (1)
3 1
Q
3
= 3，y = (1)
3
P
3
= 22，则
1253 17(22) = (125, 17) = 1。
例3 求(12345, 678)。
解 (12345, 678) = (12345, 339) = (12006, 339) = (6003, 339)
= (5664, 339) = (177, 339) = (177, 162) = (177, 81)
= (96, 81) = (3, 81) = 3。
例4 在m个盒子中放若干个硬币，然后以下述方式往这些盒子
里继续放硬币：每一次在n（n < m）个盒子中各放一个硬币。证明：
若(m, n) = 1，那么无论开始时每个盒子中有多少硬币，经过若干次放
硬币后，总可使所有盒子含有同样数量的硬币。
解 由于(m, n) = 1，所以存在整数x，y，使得mx ny = 1。因此
对于任意的自然数k，有
1 m(x kn) = n(km y)，
这样，当k充分大时，总可找出正整数x
0
，y
0
，使得
1 mx
0
= ny
0
。
上式说明，如果放y
0
次（每次放n个），那么在使m个盒子中各放x
0
个后，还多出一个硬币。把这个硬币放入含硬币最少的盒子中（这是
可以做到的），就使它与含有最多硬币的盒子所含硬币数量之差减少1。
因此经过若干次放硬币后，必可使所有盒子中的硬币数目相同。
24
习 题 五
1. 说明例1证明中所用到的四个事实的依据。
2. 用辗转相除法求整数x，y，使得1387x 162y = (1387, 162)。
3. 计算：(27090, 21672, 11352)。
4. 使用引理1中的记号，证明：(F
n + 1
, F
n
) = 1。
5. 若四个整数2836，4582，5164，6522被同一个大于1的整数
除所得的余数相同，且不等于零，求除数和余数各是多少？
6. 记M
n
= 2
n
1，证明：对于正整数a，b，有(M
a
, M
b
) = M
(a, b)
。
第六节 算术基本定理
在本节中，我们要介绍整数与素数的一个重要关系，即任何大于
1的正整数都可以表示成素数的乘积。
引理1 任何大于1的正整数n可以写成素数之积，即
n = p
1
p
2
p
m
， (1)
其中p
i
（1 i m）是素数。
证明 当n = 2时，结论显然成立。
假设对于2 n k，式(1)成立，我们来证明式(1)对于n = k 1也
成立，从而由归纳法推出式(1)对任何大于1的整数n成立。
如果k 1是素数，式(1)显然成立。
如果k 1是合数，则存在素数p与整数d，使得k 1 = pd。由于
2 d k，由归纳假定知存在素数q
1
, q
2
, , q
l
，使得d = q
1
q
2
q
l
，从
而k 1 = pq
1
q
2
q
l
。证毕。
定理1(算术基本定理) 任何大于1的整数n可以唯一地表示成
1
2
k
p
2
p
n =
p
1k
， (2)
其中p
1
, p
2
, , p
k
是素数，p
1
< p
2
< < p
k
，
1
,
2
, ,
k
是正整数。
证明 由引理1，任何大于1的整数n可以表示成式(2)的形式，
因此，只需证明表示式(2)的唯一性。
假设p
i
（1 i k）与q
j
（1 j l）都是素数，
25
p
1
p
2
p
k
，q
1
q
2
q
l
， (3)
并且
n = p
1
p
2
p
k
= q
1
q
2
q
l
， (4)
则由第三节定理4推论1，必有某个q
j
（1 j l），使得p
1
q
j
，所以
p
1
= q
j
；又有某个p
i
（1 i k），使得q
1
p
i
，所以q
1
= p
i
。于是，由式
(3)可知p
1
= q
1
，从而由式(4)得到
p
2
p
k
= q
2
q
l
。
重复上述这一过程，得到
k = l，p
i
= q
i
，1 i k
。
证毕。
定义1 使用定理1中的记号，称
1
2
k
p
2
p
n =
p
1
k
是n的标准分解式，其中p
i
（1 i k）是素数，p
1
< p
2
< < p
k
，
i
（1 i k）是正整数。
推论1 使用式(2)中的记号，有
(ⅰ) n的正因数d必有形式
k
1
2
p
2
p
k
d =
p
1
，
i
Z，0
i
i
，1 i k；
(ⅱ) n的正倍数m必有形式
k
2
p
k
m =
p
1
1
p
2
M，MN，
i
N，
i
i
，1 i k。
证明 留作习题。
推论2 设正整数a与b的标准分解式是
l
k
1
1
1
1
s
k
ap
1
p
k
q
1
q
l
，bp
1
p
k
r
1
r
s
，
其中p
i
（1 i k），q
i
（1 i l）与r
i
（1 i s）是两两不相同的素
数，
i
，
i
（1 i k），
i
（1 i l）与
i
（1 i s）都是非负整数，
则
(a, b) =
p
1
1
p
k
k
，
i
= min{
i
,
i
}，1 i k，
[a, b] =
p
1
1
p
k
k
q
1
1
q
l
l
r
1
1
r
s
s
，
i
= max{
i
,
i
}，1 i k。
证明 留作习题。
为了方便，推论2常叙述为下面的形式：
26
推论2
设正整数a与b的标准分解式是
k
1
2
1
1
k
ap
1
p
2
p
k
，bp
1
p
2
p
k
，
其中p
1
, p
2
, , p
k
是互不相同的素数，
i
，
（都是非负整数，
i
1 i k）
则
k
1
1
(a,b)p
1
p
2
p
k
，
i
min{
i
,
i
}，1ik，
k
1
1
[a,b]p
1
p
2
p
k
，
i
max{
i
,
i
}，1ik。
推论3 设a，b，c，n是正整数，
ab = c
n
，(a, b) = 1， (5)
则存在正整数u，v，使得
a = u
n
，b = v
n
，c = uv，(u, v) = 1。
k
1
1
p
2
p
k
证明 设c =
p
1
，其中p
1
, p
2
, , p
k
是互不相同的素数，
i
（1 i k）是正整数。又设
k
1
2
1
1
k
ap
1
p
2
p
k
，bp
1
p
2
p
k
，
其中
I
，
i
（1 i k）都是非负整数。由式(5)及推论2
可知
min{
i
,
i
} = 0，
i
i
= n
i
，1 i k，
因此，对于每个i（1 i k），等式
i
= n
i
，
i
= 0与
i
= 0，
i
= n
i
有且只有一个成立。这就证明了推论。证毕。
例1 写出51480的标准分解式。
解 我们有
51480 = 225740 = 2
2
12870 = 2
3
6435
= 2
3
51287 = 2
3
53429
= 2
3
53
2
143 = 2
3
3
2
51113。
例2 设a，b，c是整数，证明：
(ⅰ) (a, b)[a, b] = ab；
(ⅱ) (a, [b, c]) = [(a, b), (a, c)]。
解 为了叙述方便，不妨假定a，b，c是正整数。
(ⅰ) 设
k
1
2
1
1
k
ap
1
p
2
p
k
，bp
1
p
2
p
k
，
其中p
1
, p
2
, , p
k
是互不相同的素数，
i
，
i
（1 i k）都是非负整数。
27
由定理1推论2
，有
k
1
1
(a,b)p
1
p
2
p
k
，
i
min{
i
,
i
}，1ik，
k
1
1
[a,b]p
1
p
2
p
k
，
i
max{
i
,
i
}，1ik。
由此知
(a, b)[a, b] =
p
i
i1
k
i
i
i1
k
i
,
i
}
p
i
min{
i
,
i
}max{
p
i
i
i
=ab；
i1
k
(ⅱ) 设
a
p
i
，b
p
i
，c
p
i
i
，
i1i1i1
k
i
k
i
k
其中p
1
, p
2
, , p
k
是互不相同的素数，
i
，
i
，
i
（1 i k）都是非负
整数。由定理1推论2
，有
(a,[b,c])
p
i
i
，[(a,b),(a,c)]
p
i
i
，
i1i1
kk
其中，对于1 i k，有
i
= min{
i
, max{
i
,
i
}}，
i
= max{min{
i
,
i
}, min{
i
,
i
}}，
不妨设
i
i
，则
min{
i
,
i
} min{
i
,
i
}，
所以
i
= min{
i
,
i
} =
i
，
即(a, [b, c]) = [(a, b), (a, c)]。
注：利用定理1可以容易地处理许多像例2这样的问题。
111
例3 证明：
N1
（n 2）不是整数。
352n1
解 设
3
k
2n 1 < 3
k
+ 1
。
对于任意的1 i n，2i 1 3
k
，记
2i 1 =
3
i
Q
i
，Q
i
Z，
由第一节例5，知
i
k 1。因为3
k
1
Q
1
Q
2
Q
2n 1
是整数，所以，如
果N是整数，则存在整数Q，使得
28
3
由于3
|
Q
1
Q
2
Q
2n1
，所以上式右端不是整数，这个矛盾说明N不能
是整数。
3
k
1
Q
1
Q
2
Q
2n 1
N = Q 3
k
1
Q
1
Q
2
Q
2n 1
1
k
。
习 题 六
1. 证明定理1的推论1。
2. 证明定理1的推论2。
3. 写出22345680的标准分解式。
4. 证明：在1, 2, , 2n中任取n 1数，其中至少有一个能被另
一个整除。
11
（n 2）不是整数。
2n
6. 设a，b是正整数，证明：存在a
1
，a
2
，b
1
，b
2
，使得
a = a
1
a
2
，b = b
1
b
2
，(a
2
, b
2
) = 1，
并且[a, b] = a
2
b
2
。
5. 证明：
1
第七节 函数[x]与{x}
本节中要介绍函数[x]，它在许多数学问题中有广泛的应用。
定义1 设x是实数，以[x]表示不超过x的最大整数，称它为x
的整数部分，又称{x} = x [x]为x的小数部分。
定理1 设x与y是实数，则
(ⅰ) x y [x] [y]；
(ⅱ) 若m是整数，则[m x] = m [x]；
(ⅲ) 若0 x < 1，则[x] = 0；
若{x}{y}1
[x][y]
(ⅳ) [x y] =
；
[x][y]1若{x}{y}1
29
[x]
(ⅴ) [x] =
[x]1
0
(ⅵ) {x} =
1{x}
若xZ
若xZ
若xZ
若xZ
；
。
证明 留作习题。
定理2 设a与b是正整数，则在1, 2, , a中能被b整除的整数
有
[
a
]
个。
b
证明 能被b整除的正整数是b, 2b, 3b, ，因此，若数1, 2, , a
kb a < (k 1)b k
中能被b整除的整数有k个，则
a
a
< k 1 k =
[]
。
b
b
证毕。
由定理2我们看到，若b是正整数，那么对于任意的整数a，有
aa
ab
[]
b
{}
，
bb
即在带余数除法
a = bq r，0 r < b
aa
中有
q
[]
，rb
{}
。
bb
1
2
k
p
2
p
定理3 设n是正整数，n! =
p
1
则
k
是n!的标准分解式，
i
=
[
r1
n
p
i
r
]
。 (1)
证明 对于任意固定的素数p，以p(k)表示在k的标准分解式中的
p的指数，则
p(n!) = p(1) p(2) p(n)。
以n
j
表示p(1), p(2), , p(n)中等于j的个数，那么
p(n!) = 1n
1
2n
2
3n
3
， (2)
显然，n
j
就是在1, 2, , n中满足p
j
a并且p
j
+ 1
|
a的整数a的个
30
数，所以，由定理2有
n
j
=
[
n
p
]
[
j
n
p
j1
]
。
将上式代入式(2)，得到
nnnnnn
p(n!)1
([]
[
2
])
2
([
2
]
[
3
])
3
([
3
]
[
4
])
p
ppppp
[
r1
n
p
r
]
。
即式(1)成立。证毕。
推论 设n是正整数，则
n! =
p
r1
pn
pn
[
p
r
]
n
，
其中
表示对不超过n的所有素数p求积。
定理４ 设n是正整数，1 k n 1，则
n!
N。 (3)
C
k
n
k!(nk)!
若n是素数，则n
C
k
n
，1 k n 1。
证明 由定理3，对于任意的素数p，整数n!，k!与(n k)!的标准
分解式中所含的p的指数分别是
nknk
[]
，
[]
与
r
r
[
r
]
。
p
r1
p
r1
p
r1
利用定理1可知
nknk
[
r
]
[
r
]
[
r
]
，
p
r1
p
r1
p
r1
因此
C
k
n
是整数。
若n是素数，则对于1 k n 1，有
(n, k!) = 1，(n, (n k)!) = 1 (n, k!(n k)!) = 1，
由此及
31
C
k
n
n(n1)!
N，
k!(nk)!
推出k!(n k)!(n 1)!，从而n
C
k
n
。证毕。
例1 求最大的正整数k，使得10
k
199!。
解 由定理3，199!的标准分解式中所含的5的幂指数是
199
[
199
]
[
199
]
[]
= 47，
5
5
2
5
3
所以，所求的最大整数是k = 47。
例2 设x与y是实数，则
[2x] [2y] [x] [x y] [y]。 (4)
解 设x = [x]
，0
< 1，y = [y]
，0
< 1，则
[x] [x y] [y] = 2[x] 2[y] [
]， (5)
[2x] [2y] = 2[x] 2[y] [2
] [2
]。 (6)
如果[
] = 0，那么显然有[
] [2
] [2
]；
1
如果[
] = 1，那么
与
中至少有一个不小于，于是
2
[2
] [2
] 1 = [
]。
因此无论[
] = 0或1，都有[
] [2
] [2
]，由此及式(5)和式
(6)可以推出式(4)。
例3 设n是正整数，则
[nn1][4n2]
。 (7)
解 首先，我们有
[nn1]nn12n12n(n1)
2n12n14n2，
所以
[nn1][4n2]
。
若上式中的等号不成立，即
[nn1][4n2]
， (8)
则存在整数a，使得
[nn1]a[4n2]
，
32
因此
2n12n(n1)a
2
4n2，
22
2nna2n12n1，
(2n 1)
2
1< (a
2
2n 1)
2
(2n 1)
2
，
所以
a
2
2n 1 = 2n 1 a
2
= 4n 2。 (9)
但是，无论2a或2
|
a，式(9)都不能成立，这个矛盾说明式(8)不能成
立，即式(7)成立。
例4 设x是正数，n是正整数，则
12n1
[x]
[
x
]
[
x
]
[
x
]
= [nx]。
nnn
ii1
解 设x = [x]
，
，0 i n 1，则
nn
12n1
[x]
[
x
]
[
x
]
[
x
]
nnn
= n[x] i = n[x] [n
] = [n([x]
)] = [nx]。
例5 求[
(32)
1992
]的个位数。
解 由
(32)
2
526
得
(32)
1992
(32)
1992
9962
C
996
5
994
2
2
62
996
6
498
)
996996
=
(526)(526)
=
2(5
= 10A 2
997
6
498
= 10A 224
498
= 10A 2(25 1)
498
= 10B 2， （10）
其中A和B都是整数。由于0 < 5
26
< 1，所以，由式(10)可知
[
(32)
1996
]的个位数是1。
注：一般地，如果A，BN，A
2
> B，
AB
< 1，则由
k2
(A
B)
k
(A
B)
k
2(A
k
C
2
B
)
k
A
可以求出[
(AB)
k
]。
33
例6 设x和y是正无理数，
11
1
，证明：数列
xy
[x], [2x], , [kx], 与 [y], [2y], , [my], (11)
联合构成了整个正整数集合，而且，两个数列中的数互不相同。
解 显然x > 1，y > 1，并且x y。因此，在数列(11)中至多有一
个数等于给定的正整数n，否则存在正整数k与m，使得
n = [kx] = [my]。
因为x与y都是无理数，所以我们有
n < kx < n 1，n < my < n 1，
k1km1m
，，
n1xnn1yn
km11km
1，
n1xyn
n < k m < n 1，
这是不可能的。
下面证明，对于任意给定的正整数n，总可找到某个正整数k，使
得n等于[kx]或者[ky]。假设不然，则存在p, qN，使得
[px] < n < [(p 1)x]，[qy] < n < [(q 1)y]。
于是（因为x和y是无理数），
px < n < n 1 [(p 1)x] < (p 1)x，
qy < n < n 1 [(q 1)y] < (q 1)y，
pq11pq2
，
1
nxyn1
p q < n < n 1 < p q 2，
这是不可能的。
习 题 七
1. 证明定理1。
2. 求使12347!被35
k
整除的最大的k值。
34
n2
r1
]
= n。 3. 设n是正整数，x是实数，证明：
[
r
2
r1
4. 设n是正整数，求方程
x
2
[x
2
] = (x [x])
2
在[1, n]中的解的个数。
5. 证明：方程
f(x) = [x] [2x] [2
2
x] [2
3
x] [2
4
x] [2
5
x] = 12345
没有实数解。
6. 证明：在n!的标准分解式中，2的指数h = n k，其中k是n
的二进制表示的位数码之和。
第八节 素 数
在第六节中我们已经证明了：每个正整数可以表示成素数幂的乘
积。这就引出了一个问题：素数是否有无穷多个？如果有无穷多个，
那么，作为无穷大量，素数个数具有怎样的性状？这是数论研究中的
一个中心课题。本节要对这一问题作初步的研究。
定义1 对于正实数x，以
(x)表示不超过x的素数个数。
例如，
(15) = 6，
(10.4) = 4，
(50) = 15。
定理1 素数有无限多个。
证明 我们给出三个证明方法。
证法Ⅰ 假设只有k个素数，设它们是p
1
, p
2
, , p
k
。记
N = p
1
p
2
p
k
1。
由第一节定理2可知，N有素因数p，我们要说明p p
i
，1 i k，
从而得出矛盾。
事实上，若有某个i，1 i k，使得p = p
i
，则由
pN = p
1
p
2
p
k
1
推出p1，这是不可能的。因此在p
1
, p
2
, , p
k
之外又有一个素数p，
这与假设是矛盾的。所以素数不可能是有限个。
证法Ⅱ 我们证明整数
35
2
1，2
2
1，2
2
1，，2
2
1，
2n
是两两互素的，从而由第六节引理1可知素数有无限多个。
事实上，若m和n是整数，m > n 0，则
2
2
1(2
2
(2
2
(2
2
mm1
1)(2
2
1)(2
2
m1
1)
1)(2
2
m2m1m2
1)
mn1
1)(2
2
m2
1)
(2
2
1)(2
2
1)
nn
Q(2
2
1)，
n
此处Q是整数。因此
2
2
1Q(2
2
1)2，
mn
故
(2
2
1,2
2
1)(2,2
2
1)1。
mnn
证法Ⅲ 假设只有有限个素数p
1
, p
2
, , p
k
。由第六节定理1，每
个正整数可以写成
1
2
p
2
p
k
k
，
i
1，1 i k。 n =
p
1
由于
(
1
1
)
1
1
p
p
，
0
所以，对于任何正整数N，有
11111
1
1
(
1
)
1
(
1
)
(
1
1
)
1
。
23Np
1
p
2
p
k
当N 时，上式左端是一个无穷大量，右端是有限的，这个矛盾说
明素数不能是有限多个。证毕。
注1：形如
2
2
1
（n = 0, 1, 2, ）的数称为Fermat数。Fermat
曾经猜测它们都是素数。这是错误的，因为尽管F
0
，F
1
，F
2
，F
3
，F
4
都是素数，F
5
=
2
2
16416700417
却是合数。
注2：将全体素数按大小顺序排列为
p
1
= 2，p
2
= 3，p
3
= 5，p
4
，，p
n
，，
36
5
n
那么由第一个证明方法可以看出
p
n + 1
p
1
p
2
p
n
1，n 1。
定理2 对于n 1，
1
(ⅰ)
(n) log
2
n；
2
n
2
(ⅱ) p
n
2。
证明 (ⅰ) 设n是大于1的正整数。由算术基本定理，对于任
意的整数k，1 k n，都有整数a和b，使得k = a
2
b，其中整数b不
能被任何大于1的整数的平方整除。现在，我们来看使得
k = a
2
b，1 k n (1)
即1 a
2
b n成立的整数a，b有多少对。首先，整数a的个数
n
；
其次，由于b n并且不含有平方因数，所以，整数b的因数只可能是
不超过n的不同的素数的乘积，因此，整数b的个数 2
(
n
)
。这样，
使得式(1)成立的整数a和b至多是
n
2
(
n
)
对，所以，n
n
2
(
n
)
，即
1
(n) log
2
n。
2
(ⅱ) 以p
m
表示第m个素数，在结论(ⅰ)中取n = p
m
，我们得到m
1
log
2
p
m
，由此即可得到结论(ⅱ)。证毕。
2
注：定理2对于无穷大量
(x)的下界估计是相当粗糙的。下面的
定理是已经知道的（由于其证明较繁，故本书中不予证明）。
定理3(素数定理) 我们有
x
(x) ，（x），
logx
此处logx是以e为底的x的对数。
推论 以p
n
表示第n个素数，则
p
n
nlogn（n）。
证明 由定理3，当n 时，有
p
n
n 。 (2)
logp
n
因此
37
nlogp
n
p
n
，
logn loglogp
n
logp
n
，
logn logp
n
。
由上式与式(2)得p
n
nlogn（n）。证毕。
例1 若a > 1，a
n
1是素数，则a = 2，并且n是素数。
解 若a > 2，则由
a
n
1 = (a 1)(a
n
1
a
n
2
1)
可知a
n
1是合数。所以a = 2。
若n是合数，则n = xy，x > 1，y > 1，于是由
2
xy
1 = (2
x
1)(2
x
(
y
1)
2
x
(
y
2)
1)
以及2
x
1 > 1可知2
n
1是合数，所以2
n
1是素数时，n必是素数。
n
注：若n是素数，则称2 1是Mersenne数。
例2 形如4n 3的素数有无限多个。
解 若不然，假设只有k个形如4n 3的素数p
1
, p
2
, , p
k
。记
N = 4p
1
pp
k
– 1。
由第六节引理1，正整数N可以写成若干个素数之积。我们指出，
这些素因数中至少有一个是4n 3形式。否则，若它们都是4n 1的
形式，则N也是4n 1的形式，这与N的定义矛盾。以p表示这个素
因数，则p p
i
，1 i k。否则若有某个i，1 i k，使得p = p
i
，则
由pN推出p1，这是不可能的。因此在p
1
, p
2
, , p
k
之外又存在一个
形如4n 3的素数p，这与原假设矛盾，所以形如4n 3的素数有无
限多个。
例3 设f(x) = a
k
x
k
a
k 1
x
k
1
a
0
是整系数多项式，那么，
存在无穷多个正整数n，使得f(n)是合数。
解 不妨假定a
k
> 0。于是f(x) （x ），因此，存在正整
数N，使得当n > N时，有f(n) > 1。取整数x > N，记
y = f(x) = a
k
x
k
a
k 1
x
k
1
a
0
，
又设r是任意的正整数，n = ry x，则
f(n) = f(ry x) = a
k
(ry x)
k
a
k 1
(ry x)
k
1
a
0
= yQ f(x) = y(Q 1)
38
是合数。
习 题 八
1. 证明：若2
n
1是素数，则n是2的乘幂。
2. 证明：若2
n
1是素数，则n是素数。
3. 证明：形如6n 5的素数有无限多个。
4. 设d 是正整数，6
|
d，证明：在以d为公差的等差数列中，
连续三项都是素数的情况最多发生一次。
5. 证明：对于任意给定的正整数n，必存在连续的n个自然数，
使得它们都是合数。
1
6. 证明：级数
发散，此处使用了定理1注2中的记号。
n1
p
n
39
2024年3月17日发(作者：束冬易)
第一章 整除理论
整除性理论是初等数论的基础。本章要介绍带余数除法，辗转相
除法，最大公约数，最小公倍数，算术基本定理以及它们的一些应用。
第一节 数的整除性
定义1 设a，b是整数，b 0，如果存在整数c，使得
a = bc
成立，则称a被b整除，a是b的倍数，b是a的约数（因数或除数），
并且使用记号ba；如果不存在整数c使得a = bc成立，则称a不被b
整除，记为b
|
a。
显然每个非零整数a都有约数 1，a，称这四个数为a的平凡约
数，a的另外的约数称为非平凡约数。
被2整除的整数称为偶数，不被2整除的整数称为奇数。
定理1 下面的结论成立：
(ⅰ) ab ab；
(ⅱ) ab，bc ac；
(ⅲ) ba
i
，i = 1, 2, , k ba
1
x
1
a
2
x
2
a
k
x
k
，此处x（
i
i =
1, 2, , k）是任意的整数；
(ⅳ) ba bcac，此处c是任意的非零整数；
(ⅴ) ba，a 0 |b| |a|；ba且|a| < |b| a = 0。
证明 留作习题。
定义2 若整数a 0，1，并且只有约数 1和 a，则称a是素
数（或质数）；否则称a为合数。
以后在本书中若无特别说明，素数总是指正素数。
定理2 任何大于1的整数a都至少有一个素约数。
1
证明 若a是素数，则定理是显然的。
若a不是素数，那么它有两个以上的正的非平凡约数，设它们是
d
1
, d
2
, , d
k
。不妨设d
1
是其中最小的。若d
1
不是素数，则存在e
1
> 1，
e
2
> 1，使得d
1
= e
1
e
2
，因此，e
1
和e
2
也是a的正的非平凡约数。这与
d
1
的最小性矛盾。所以d
1
是素数。证毕。
推论 任何大于1的合数a必有一个不超过
a
的素约数。
证明 使用定理2中的记号，有a = d
1
d
2
，其中d
1
> 1是最小的素
约数，所以d
1
2
a。证毕。
例1 设r是正奇数，证明：对任意的正整数n，有
n 2
|
1
r
2
r
n
r
。
解 对于任意的正整数a，b以及正奇数k，有
a
k
b
k
= (a b)(a
k
1
a
k
2
b a
k
3
b
2
b
k
1
) = (a b)q，
其中q是整数。记s = 1
r
2
r
n
r
，则
2s = 2 (2
r
n
r
) (3
r
(n 1)
r
) (n
r
2
r
) = 2 (n 2)Q，
其中Q是整数。若n 2s，由上式知n 22，因为n 2 > 2，这是
不可能的，所以n 2
|
s。
例2 设A = { d
1
, d
2
, , d
k
}是n的所有约数的集合，则
B =
{
nnn
,,
,
}
d
1
d
2
d
k
也是n的所有约数的集合。
解 由以下三点理由可以证得结论：
(ⅰ) A和B的元素个数相同；
n
(ⅱ) 若d
i
A，即d
i
n，则
|
n，反之亦然；
d
i
nn
(ⅲ) 若d
i
d
j
，则。
d
i
d
j
例3 以d(n)表示n的正约数的个数，例如：d(1) = 1，d(2) = 2，
d(3) = 2，d(4) = 3，
。问：
d(1) d(2) d(1997)
2
是否为偶数？
n
，因此，n的正约数d与
d
nnn
是成对地出现的。只有当d =，即n = d
2
时，d和才是同一个数。
ddd
故当且仅当n是完全平方数时，d(n)是奇数。
因为44
2
< 1997 < 45
2
，所以在d(1), d(2), , d(1997)中恰有44个
解 对于n的每个约数d，都有n = d
奇数，故d(1) d(2) d(1997)是偶数。
例4 设凸2n边形M的顶点是A
1
, A
2
, , A
2n
，点O在M的内部，
用1, 2, , 2n将M的2n条边分别编号，又将OA
1
, OA
2
, , OA
2n
也同
样进行编号，若把这些编号作为相应的线段的长度，证明：无论怎么
编号，都不能使得三角形OA
1
A
2
, OA
2
A
3
, , OA
2n
A
1
的周长都相等。
解 假设这些三角形的周长都相等，记为s。则
2ns = 3(1 2 2n) = 3n(2n 1)，
即
2s = 3(2n 1)，
因此23(2n 1)，这是不可能的，这个矛盾说明这些三角形的周长不
可能全都相等。
例5 设整数k 1，证明：
(ⅰ) 若2
k
n < 2
k
1
，1 a n，a 2
k
，则2
k
|
a；
(ⅱ) 若3
k
2n
1 < 3
k
+ 1
，1 b n，2b
1 3
k
，则3
k
|
2b
1。
解 (ⅰ) 若2
k
|a
，
则存在整数q，使得a= q2
k
。显然q只可能是
0或1。此时a= 0或2
k
，这都是不可能的，所以2
k
|
a；
(ⅱ) 若 3
k
|2b-1，则存在整数q，使得2b-1= q3
k
，显然q只可能
是0，1, 或2。此时2b-1= 0，3
k
，或
23
，这都是不可能的，所以
3
k
|
2b
1。
例6 写出不超过100的所有的素数。
解 将不超过100的正整数排列如下：
1 2 3 4 5 6 7 8 9 10
3
k
11 12 13 14 15 16 17 18 19 20
21 22 23 24 25 26 27 28 29 30
31 32 33 34 35 36 37 38 39 40
41 42 43 44 45 46 47 48 49 50
51 52 53 54 55 56 57 58 59 60
61 62 63 64 65 66 67 68 69 70
71 72 73 74 75 76 77 78 79 80
81 82 83 84 85 86 87 88 89 90
91 92 93 94 95 96 97 98 99 100
按以下步骤进行：
(ⅰ) 删去1，剩下的后面的第一个数是2，2是素数；
(ⅱ) 删去2后面的被2整除的数，剩下的2后面的第一个数是3，
3是素数；
(ⅲ) 再删去3后面的被3整除的数，剩下的3后面的第一个数
是5，5是素数；
(ⅳ) 再删去5后面的被5整除的数，剩下的5后面的第一个数
是7，7是素数；
照以上步骤可以依次得到素数2, 3, 5, 7, 11, 。
由定理2推论可知，不超过100的合数必有一个不超过10的素约
数，因此在删去7后面被7整除的数以后，就得到了不超过100的全
部素数。
在例6中所使用的寻找素数的方法，称为Eratosthenes筛法。它可
以用来求出不超过任何固定整数的所有素数。在理论上这是可行的；
但在实际应用中，这种列出素数的方法需要大量的计算时间，是不可
取的。
例7 证明：存在无穷多个正整数a，使得
n
4
a（n = 1, 2, 3, ）
都是合数。
解 取a = 4k
4
，对于任意的nN，有
n
4
4k
4
= (n
2
2k
2
)
2
4n
2
k
2
= (n
2
2k
2
2nk)(n
2
2k
2
2nk)。
因为
4
n
2
2k
2
2nk = (n k)
2
k
2
k
2
，
所以，对于任意的k = 2, 3, 以及任意的nN，n
4
a是合数。
例8 设a
1
, a
2
, , a
n
是整数，且
a
1
a
2
a
n
= 0，a
1
a
2
a
n
= n，
则4n。
解 如果2
|
n，则n, a
1
, a
2
, , a
n
都是奇数。于是a
1
a
2
a
n
是奇数个奇数之和，不可能等于零，这与题设矛盾，所以2n，即在
a
1
, a
2
, , a
n
中至少有一个偶数。如果只有一个偶数，不妨设为a
1
，那
么2
。此时有等式
|
a
i
（2 i n）
a
2
a
n
= a
1
，
在上式中，左端是(n 1)个奇数之和，右端是偶数，这是不可能的，
因此，在a
1
, a
2
, , a
n
中至少有两个偶数，即4n。
例9 若n是奇数，则8n
2
1。
解 设n = 2k 1，则
n
2
1= (2k 1)
2
1 = 4k(k 1)。
在k和k 1中有一个是偶数，所以8n
2
1。
例9的结论虽然简单，却是很有用的。例如，使用例3中的记号，
我们可以提出下面的问题：
问题 d(1)
2
d(2)
2
d(1997)
2
被4除的余数是多少？
例10 证明：方程
a
1
2
a
2
2
a
3
2
= 1999 (1)
无整数解。
解 若a
1
，a
2
，a
3
都是奇数，则存在整数A
1
，A
2
，A
3
，使得
a
1
2
= 8A
1
1，a
2
2
= 8A
2
1，a
3
2
= 8A
3
1，
于是
a
1
2
a
2
2
a
3
2
= 8(A
1
A
2
A
3
) 3。
由于1999被8除的余数是7，所以a
1
，a
2
，a
3
不可能都是奇数。
由式(1)，a
1
，a
2
，a
3
中只能有一个奇数，设a
1
为奇数，a
2
，a
3
为
偶数，则存在整数A
1
，A
2
，A
3
，使得
a
1
2
= 8A
1
1，a
2
2
= 8A
2
r，a
3
2
= 8A
3
s，
5
于是
a
1
2
a
2
2
a
3
2
= 8(A
1
A
2
A
3
) 1 r s，
其中r和s是整数，而且只能取值0或4。这样a
1
2
a
2
2
a
3
2
被8除的
余数只可能是1或5，但1999被8除的余数是7，所以这样的a
1
，a
2
，
a
3
也不能使式(2)成立。
综上证得所需要的结论。
习 题 一
1. 证明定理1。
2. 证明：若m pmn pq，则m pmq np。
3. 证明：任意给定的连续39个自然数，其中至少存在一个自然
数，使得这个自然数的数字和能被11整除。
4. 设p是n的最小素约数，n = pn
1
，n
1
> 1，证明：若p >
3
n
，
则n
1
是素数。
5. 证明：存在无穷多个自然数n，使得n不能表示为
a
2
p（a > 0是整数，p为素数）
的形式。
第二节 带余数除法
在本节中，我们要介绍带余数除法及其简单应用。
定理1(带余数除法) 设a与b是两个整数，b 0，则存在唯一的
两个整数q和r，使得
a = bq r，0 r < |b|。 (1)
|
a，考虑证明 存在性 若ba，a = bq，qZ，可取r = 0。若b
集合
A = { a kb；kZ },
其中Z表示所有整数的集合，以后，仍使用此记号，并以N表示所有
正整数的集合。
在集合A中有无限多个正整数，设最小的正整数是r = a k
0
b，则
6
必有
0 < r < |b|， (2)
否则就有r |b|。因为b
|
a，所以r |b|。于是r > |b|，即a k
0
b > |b|，
a k
0
b
|b| > 0，这样，在集合A中，又有正整数a k
0
b
|b| < r，这
与r的最小性矛盾。所以式(2)必定成立。取q =
k
0
知式(1)成立。存
在性得证。
唯一性 假设有两对整数q
，r
与q
，r
都使得式(1)成立，即
a = q
b r
= q
b r
，0 r
, r
< |b|，
则
(q
q
)b = r
r
，|r
r
| < |b|， (3)
因此r
r
= 0，r
= r
，再由式(3)得出q
= q
，唯一性得证。证毕。
定义1 称式(1)中的q是a被b除的商，r是a被b除的余数。
由定理1可知，对于给定的整数b，可以按照被b除的余数将所
有的整数分成b类。在同一类中的数被b除的余数相同。这就使得许
多关于全体整数的问题可以归化为对有限个整数类的研究。
以后在本书中，除特别声明外，在谈到带余数除法时总是假定b
是正整数。
例1 设a，b，x，y是整数，k和m是正整数，并且
a = a
1
m r
1
，0 r
1
< m，
b = b
1
m r
2
，0 r
2
< m，
则ax by和ab被m除的余数分别与r
1
x r
2
y和r
1
r
2
被m除的余数相
同。特别地，a
k
与r
1
k
被m除的余数相同。
解 由
ax by = (a
1
m r
1
)x (b
1
m r
2
)y = (a
1
x b
1
y)m r
1
x r
2
y
可知，若r
1
x r
2
y被m除的余数是r，即
r
1
x r
2
y = qm r，0 r < m，
则
ax by = (a
1
x b
1
y q)m r，0 r < m，
即ax by被m除的余数也是r。
同样方法可以证明其余结论。
例2 设a
1
, a
2
, , a
n
为不全为零的整数，以y
0
表示集合
A = { y；y = a
1
x
1
a
n
x
n
，x
i
Z，1 i n }
7
中的最小正数，则对于任何yA，y
0
y；特别地，y
0
a
i
，1 i n。
解 设y
0
= a
1
x
1
a
n
x
n
，对任意的y = a
1
x
1
a
n
x
n
A，由
定理1，存在q, r
0
Z，使得
y = qy
0
r
0
，0 r
0
< y
0
。
因此
r
0
= y
qy
0
= a
1
(x
1
qx
1
) a
n
(x
n
qx
n
)A。
如果r
0
0，那么，因为0 < r
0
< y
0
，所以r
0
是A中比y
0
还小的正
数，这与y
0
的定义矛盾。所以r
0
= 0，即y
0
y。
显然a
i
A（1 i n），所以y
0
整除每个a
i
（1 i n）。
例3 任意给出的五个整数中，必有三个数之和被3整除。
解 设这五个数是a
i
，i = 1, 2, 3, 4, 5，记
a
i
= 3q
i
r
i
，0 r
i
< 3，i = 1, 2, 3, 4, 5。
分别考虑以下两种情形：
(ⅰ) 若在r
1
, r
2
, , r
5
中数0，1，2都出现，不妨设r
1
= 0，r
2
= 1，
r
3
= 2，此时
a
1
a
2
a
3
= 3(q
1
q
2
q
3
) 3
可以被3整除；
(ⅱ) 若在r
1
, r
2
, , r
5
中数0，1，2至少有一个不出现，这样至
少有三个r
i
要取相同的值，不妨设r
1
= r
2
= r
3
= r（r = 0，1或2），此
时
a
1
a
2
a
3
= 3(q
1
q
2
q
3
) 3r
可以被3整除。
例4 设a
0
, a
1
, , a
n
Z，f(x) = a
n
x
n
a
1
x a
0
，已知f(0)与
f(1)都不是3的倍数，证明：若方程f(x) = 0有整数解，则
3f(
1) = a
0
a
1
a
2
(
1)
n
a
n
。
解 对任何整数x，都有
x = 3q r，r = 0，1或2，qZ。
(ⅰ) 若r = 0，即x = 3q，qZ，则
f(x) = f(3q) = a
n
(3q)
n
a
1
(3q) a
0
= 3Q
1
a
0
= 3Q
1
f(0)，
其中Q
1
Z，由于f(0)不是3的倍数，所以f(x) 0；
(ⅱ) 若r = 1，即x = 3q 1，qZ，则
8
f(x) = f(3q 1) = a
n
(3q 1)
n
a
1
(3q 1) a
0
= 3Q
2
a
n
a
1
a
0
= 3Q
2
f(1)，
其中Q
2
Z。由于f(1)不是3的倍数，所以f(x) 0。
因此若f(x) = 0有整数解x，则必是x = 3q 2 = 3q
1，q
Z，于
是
0 = f(x) = f(3q
1) = a
n
(3q
1)
n
a
1
(3q
1) a
0
= 3Q
3
a
0
a
1
a
2
(
1)
n
a
n
= 3Q
3
f(
1)，
其中Q
3
Z。所以3f(
1) = a
0
a
1
a
2
(
1)
n
a
n
。
例5 证明：对于任意的整数n，f(n) = 3n
5
5n
3
7n被15整除。
解 对于任意的正整数n，记
n = 15q r，0 r < 15。
由例1，
n
2
= 15Q
1
r
1
，n
4
= 15Q
2
r
2
，
其中r
1
与r
2
分别是r
2
与r
4
被15除的余数。
以R表示3n
4
5n
2
7被15除的余数，则R就是3r
2
5r
1
7被
15除的余数，而且f(n)被15除的余数就是rR被15除的余数，记为R
。
当r = 0时，显然R
= 0，即153n
5
5n
3
7n。
对于r = 1, 2, 3, , 14的情形，通过计算列出下表：
r = 1, 14 2, 13 3, 12 4, 11 5, 10 6, 9 7, 8
r
1
= 1 4 9 1 10 6 4
r
2
= 1 1 6 1 10 6 1
R = 0 0 10 0 12 10 0
R= 0 0 0 0 0 0 0
这证明了结论。
例6 设n是奇数，则16n
4
4n
2
11。
解 我们有
n
4
4n
2
11 = (n
2
1)(n
2
5) 16。
由第一节例题9，有8n
2
1，由此及2n
2
5得到16(n
2
1)(n
2
5)。
例7 证明：若a被9除的余数是3，4，5或6，则方程x
3
y
3
=
9
a没有整数解。
解 对任意的整数x，y，记
x = 3q
1
r
1
，y = 3q
2
r
2
，0 r
1
, r
2
< 3。
则存在Q
1
, R
1
, Q
2
, R
2
Z，使得
x
3
= 9Q
1
R
1
，y
3
= 9Q
2
R
2
，
其中R
1
和R
2
被9除的余数分别与r
1
3
和r
2
3
被9除的余数相同，即
R
1
= 0，1或8，R
2
= 0，1或8。 (4)
因此
x
3
y
3
= 9(Q
1
Q
2
) R
1
R
2
。
又由式(4)可知，R
1
R
2
被9除的余数只可能是0，1，2，7或8，所以，
x
3
y
3
不可能等于a
。
习 题 二
1. 证明：12n
4
2n
3
11n
2
10n，nZ。
2. 设3a
2
b
2
，证明：3a且3b。
3. 设n，k是正整数，证明：n
k
与n
k
+ 4
的个位数字相同。
4. 证明：对于任何整数n，m，等式n
2
(n 1)
2
= m
2
2不可能
成立。
5. 设a是自然数，问a
4
3a
2
9是素数还是合数？
6. 证明：对于任意给定的n个整数，必可以从中找出若干个作
和，使得这个和能被n整除。
第三节 最大公约数
定义1 整数a
1
, a
2
, , a
k
的公共约数称为a
1
, a
2
, , a
k
的公约数。
不全为零的整数a
1
, a
2
, , a
k
的公约数中最大的一个叫做a
1
, a
2
, , a
k
的最大公约数（或最大公因数），记为(a
1
, a
2
, , a
k
)。
由于每个非零整数的约数的个数是有限的，所以最大公约数是存
在的，并且是正整数。
10
如果(a
1
, a
2
, , a
k
) = 1，则称a
1
, a
2
, , a
k
是互素的（或互质的）；
如果
(a
i
, a
j
) = 1，1 i, j k，i j，
则称a
1
, a
2
, , a
k
是两两互素的（或两两互质的）。
显然，a
1
, a
2
, , a
k
两两互素可以推出(a
1
, a
2
, , a
k
) = 1，反之则不
然，例如(2, 6, 15) = 1，但(2, 6) = 2。
定理1 下面的等式成立：
(ⅰ) (a
1
, a
2
, , a
k
) = (|a
1
|, |a
2
|, , |a
k
|)；
(ⅱ) (a, 1) = 1，(a, 0) = |a|，(a, a) = |a|；
(ⅲ) (a, b) = (b, a)；
(ⅳ) 若p是素数，a是整数，则(p, a) = 1或pa；
(ⅴ) 若a = bq r，则(a, b) = (b, r)。
证明 (ⅰ)(ⅳ)留作习题。
(ⅴ) 由第一节定理1可知，如果da，db，则有dr = a bq，
反之，若db，dr，则da = bq r。因此a与b的全体公约数的集
合就是b与r的全体公约数的集合，这两个集合中的最大正数当然相
等，即(a, b) = (b, r)。证毕。
由定理1可知，在讨论(a
1
, a
2
, , a
n
)时，不妨假设a
1
, a
2
, , a
n
是
正整数，以后我们就维持这一假设。
定理2 设a
1
, a
2
, , a
k
Z，记
A = { y；y =
a
i
x
i
，x
i
Z， i k }。
i1
k
如果y
0
是集合A中最小的正数，则y
0
= (a
1
, a
2
, , a
k
)。
证明 设d是a
1
, a
2
, , a
k
的一个公约数，则dy
0
，所以d y
0
。
另一方面，由第二节例2知，y
0
也是a
1
, a
2
, , a
k
的公约数。因此y
0
是a
1
, a
2
, , a
k
的公约数中的最大者，即y
0
= ( a
1
, a
2
, , a
k
)。证毕。
推论1 设d是a
1
, a
2
, , a
k
的一个公约数，则d(a
1
, a
2
, , a
k
)。
这个推论对最大公约数的性质做了更深的刻划：最大公约数不但
是公约数中的最大的，而且是所有公约数的倍数。
11
推论2 (ma
1
, ma
2
, , ma
k
) = |m|(a
1
, a
2
, , a
k
)。
推论3 记
= (a
1
, a
2
, , a
k
)，则
(
特别地,
a
a
1
a
2
,,
,
k
)
= 1，
(
ab
,
)
= 1。
(a,b)(a,b)
定理3 (a
1
, a
2
, , a
k
) = 1的充要条件是存在整数x
1
, x
2
, , x
k
，使
得
a
1
x
1
a
2
x
2
a
k
x
k
= 1。 (1)
证明 必要性 由定理2得到。
充分性 若式(1)成立，如果 (a
1
, a
2
, , a
k
) = d > 1，那么由da
i
（1 i
k）推出da
1
x
1
a
2
x
2
a
k
x
k
= 1，这是不可能的。所以有(a
1
, a
2
, ,
a
k
) = 1。证毕。
定理4 对于任意的整数a，b，c，下面的结论成立：
(ⅰ) 由bac及(a, b) = 1可以推出bc；
(ⅱ) 由bc，ac及(a, b) = 1可以推出abc。
证明 (ⅰ) 若(a, b) = 1，由定理2，存在整数x与y，使得
ax by = 1。
因此
acx bcy = c。 (2)
由上式及bac得到bc。结论(ⅰ)得证；
(ⅱ) 若(a, b) = 1，则存在整数x，y使得式(2)成立。由bc与ac
得到abac，abbc，再由式(2)得到abc。结论(ⅱ)得证。证毕。
推论1 若p是素数，则下述结论成立：
(ⅰ) pab pa或pb；
(ⅱ) pa
2
pa。
证明 留作习题。
推论2 若 (a, b) = 1，则(a, bc) = (a, c)。
证明 设d是a与bc的一个公约数，则da，dbc，由式（2）
得到，d|c, 即d是a与c的公约数。另一方面，若d是a与c的公约
数，则它也是a与bc的公约数。因此，a与c的公约数的集合，就是
12
a与bc的公约数的集合，所以(a, bc) = (a, c)。证毕。
推论3 若 (a, b
i
) = 1，1 i n，则(a, b
1
b
2
b
n
) = 1。
证明 留作习题。
定理5 对于任意的n个整数a
1
, a
2
, , a
n
，记
(a
1
, a
2
) = d
2
，(d
2
, a
3
) = d
3
，，(d
n 2
, a
n 1
) = d
n 1
，(d
n 1
, a
n
) = d
n
，
则
d
n
= (a
1
, a
2
, , a
n
)。
证明 由定理2的推论，我们有
d
n
= (d
n 1
, a
n
) d
n
a
n
，d
n
d
n 1
，
d
n 1
= (d
n 2
, a
n 1
) d
n 1
a
n 1
，d
n 1
d
n 2
，
d
n
a
n
，d
n
a
n 1
，d
n
d
n 2
，
d
n 2
= (d
n 3
, a
n 2
) d
n 2
a
n 2
，d
n 2
d
n 3
d
n
a
n
，d
n
a
n 1
，d
n
a
n 2
，d
n
d
n 3
，
d
2
= (a
1
, a
2
) d
n
a
n
，d
n
a
n 1
，，d
n
a
2
，d
n
a
1
，
即d
n
是a
1
, a
2
, , a
n
的一个公约数。
另一方面，对于a
1
, a
2
, , a
n
的任何公约数d，由定理2的推论及
d
2
, , d
n
的定义，依次得出
da
1
，da
2
dd
2
，
dd
2
，da
3
dd
3
，
dd
n 1
，da
n
dd
n
，
因此d
n
是a
1
, a
2
, , a
n
的公约数中的最大者，即d
n
= (a
1
, a
2
, , a
n
)。证
毕。
例1 证明：若n是正整数，则
21n4
是既约分数。
14n3
解 由定理1得到
(21n 4, 14n 3) = (7n 1, 14n 3) = (7n 1, 1) = 1。
注：一般地，若(x, y) = 1，那么，对于任意的整数a，b，有
13
(x, y) = (x ay, y) = (x ay, y b(x ay)) = (x ay, (ab 1)y bx)，
xay
因此，是既约分数。
(ab1)ybx
例2 证明：121
|
n
2
2n 12，nZ。
解 由于121 = 11
2
，n
2
2n 12 = (n 1)
2
11，所以，若
11
2
(n 1)
2
11， (3)
则11(n 1)
2
，因此，由定理4的推论1得到
11n 1，11
2
(n 1)
2
。
再由式(3)得到
11
2
11，
这是不可能的。所以式(3)不能成立。
注：这个例题的一般形式是：
设p是素数，a，b是整数，则
p
k
|
(an b)
k
p
k
1
c，
其中c是不被p整除的任意整数，k是任意的大于1的整数。
例3 设a，b是整数，且
9a
2
ab b
2
， (4)
则3(a, b)。
解 由式(4)得到
9(a b)
2
3ab 3(a b)
2
3ab
3(a b)
2
3a b (5)
9(a b)
2
。
再由式(4)得到
93ab 3ab。
因此，由定理4的推论1，得到
3a或3b。
若3a，由式(5)得到3b；若3b，由(5)式也得到3a。因此，
总有3a且3b。
由定理2的推论推出3(a, b)。
|
2
a
1。 例4 设a和b是正整数，b > 2，则2
b
1
解 (ⅰ) 若a < b，且
2
b
12
a
1。 (6)
14
成立，则
2
b
1 2
a
1 2
b
2
a
2 2
a
(2
b
a
1) 2，
于是a = 1，b a = 1，即b = 2，这是不可能的，所以式(6)不成立。
(ⅱ) 若a = b，且式(6)成立，则由式(6)得到
2
a
1(2
a
1) 2 2
a
12 2
a
1 2 2
a
3，
于是b = a = 1，这是不可能的，所以式(6)不成立。
(ⅲ) 若a > b，记a = kb r，0 r < b，此时
2
kb
1 = (2
b
1)(2
(
k
1)
b
2
(
k
2)
b
1) = (2
b
1)Q，
其中Q是整数。所以
2
a
1 = 2
kb + r
1 = 2
r
(2
kb
1 1) 1
rbbr
= 2((2 1)Q 1) 1 = (2 1)Q (2 1)，
其中Q是整数。因此
2
b
12
a
1 2
b
12
r
1，
在(ⅰ)中已经证明这是不可能的，所以式(6)不能成立。
综上证得2
b
1
|
2
a
1。
习 题 三
1. 证明定理1中的结论(ⅰ)—(ⅳ)。
2. 证明定理2的推论1, 推论2和推论3。
3. 证明定理4的推论1和推论3。
4. 设x，yZ，172x 3y，证明：179x 5y。
5. 设a，b，cN，c无平方因子，a
2
b
2
c，证明：ab。
32n1
6. 设n是正整数，求
C
1
2n
,C
2n
,
,C
2n
的最大公约数。
第四节 最小公倍数
定义1 整数a
1
, a
2
, , a
k
的公共倍数称为a
1
, a
2
, , a
k
的公倍数。
a
1
, a
2
, , a
k
的正公倍数中的最小的一个叫做a
1
, a
2
, , a
k
的最小公倍
15
数，记为[a
1
, a
2
, , a
k
]。
定理1 下面的等式成立：
(ⅰ) [a, 1] = |a|，[a, a] = |a|；
(ⅱ) [a, b] = [b, a]；
(ⅲ) [a
1
, a
2
, , a
k
] = [|a
1
|, |a
2
| , |a
k
|]；
(ⅳ) 若ab，则[a, b] = |b|。
证明 留作习题。
由定理1中的结论(ⅲ)可知，在讨论a
1
, a
2
, , a
k
的最小公倍数时，
不妨假定它们都是正整数。在本节中总是维持这一假定。
最小公倍数和最大公约数之间有一个很重要的关系，即下面的定
理。
定理2 对任意的正整数a，b，有
ab
[a, b] =。
(a,b)
证明 设m是a和b的一个公倍数，那么存在整数k
1
，k
2
，使得
m = ak
1
，m = bk
2
，因此
ak
1
= bk
2
。 (1)
于是
ab
k
1
k
2
。
(a,b)(a,b)
ab
由于
(
,
)
= 1，所以由第三节定理4得到
(a,b)(a,b)
b
|
k
1
，即k
1
b
t
，
(a,b)(a,b)
其中t是某个整数。将上式代入式(1)得到
ab
m =t
。 (2)
(a,b)
另一方面，对于任意的整数t，由式(2)所确定的m显然是a与b
的公倍数，因此a与b的公倍数必是式(2)中的形式，其中t是整数。
当t = 1时，得到最小公倍数
16
[a, b] =
ab
。
(a,b)
证毕。
推论1 两个整数的任何公倍数可以被它们的最小公倍数整除。
证明 由式(2)可得证。证毕。
这个推论说明：两个整数的最小公倍数不但是最小的正倍数，而
且是另外的公倍数的约数。
推论2 设m，a，b是正整数，则[ma, mb] = m[a, b]。
证明 由定理2及第三节定理2的推论得到
m
2
abm
2
abmab
[ma, mb] == m[a, b]。
(ma,mb)m(a,b)(a,b)
证毕。
定理3 对于任意的n个整数a
1
, a
2
, , a
n
，记
[a
1
, a
2
] = m
2
，[m
2
, a
3
] = m
3
，，[m
n2
, a
n1
] = m
n1
，[m
n1
, a
n
] = m
n
，
则
[a
1
, a
2
, , a
n
] = m
n
。
证明 我们有
m
n
= [m
n1
, a
n
] m
n1
m
n
，a
n
m
n
，
m
n1
= [m
n2
, a
n1
] m
n2
m
n1
m
n
，a
n
m
n
，a
n1
m
n1
m
n
，
m
n2
= [m
n3
, a
n2
] m
n3
m
n2
m
n
，a
n
m
n
，a
n1
m
n
，a
n2
m
n
，
m
2
= [a
1
, a
2
] a
n
m
n
，，a
2
m
n
，a
1
m
n
，
即m
n
是a
1
, a
2
, , a
n
的一个公倍数。
另一方面，对于a
1
, a
2
, , a
n
的任何公倍数m，由定理2的推论及
m
2
, , m
n
的定义，得
m
2
m，m
3
m，，m
n
m。
即m
n
是a
1
, a
2
, , a
n
最小的正的公倍数。证毕。
推论 若m是整数a
1
, a
2
, , a
n
的公倍数，则[a
1
, a
2
, , a
n
]m
。
证明 留作习题。
17
定理4 整数a
1
, a
2
, , a
n
两两互素，即
(a
i
, a
j
) = 1，1 i, j n，i j
的充要条件是
[a
1
, a
2
, , a
n
] = a
1
a
2
a
n
。 (3)
证明 必要性 因为(a
1
, a
2
) = 1，由定理2得到
aa
[a
1
, a
2
] =
12
= a
1
a
2
。
(a
1
,a
2
)
由(a
1
, a
3
) = (a
2
, a
3
) = 1及第三节定理4推论3得到
(a
1
a
2
, a
3
) = 1，
由此及定理3得到
[a
1
, a
2
, a
3
] = [[a
1
, a
2
], a
3
] = [a
1
a
2
, a
3
] = a
1
a
2
a
3
。
如此继续下去，就得到式(3)。
充分性 用归纳法证明。当n = 2时，式(3)成为[a
1
, a
2
] = a
1
a
2
。由
定理2
aa
a
1
a
2
= [a
1
, a
2
] =
12
(a
1
, a
2
) = 1，
(a
1
,a
2
)
即当n = 2时，充分性成立。
假设充分性当n = k时成立，即
[a
1
, a
2
, , a
k
] = a
1
a
2
a
k
(a
i
, a
j
) = 1，1 i, j k，i j。
对于整数a
1
, a
2
, , a
k
, a
k + 1
，使用定理3中的记号，由定理3可知
[a
1
, a
2
, , a
k
, a
k + 1
] = [m
k
, a
k + 1
]。 (4)
其中m
k
= [a
1
, a
2
, , a
k
]。因此，如果
[a
1
, a
2
, , a
k
, a
k + 1
] = a
1
a
2
a
k
a
k + 1
，
那么，由此及式(4)得到
[a
1
, a
2
, , a
k
, a
k + 1
] = [m
k
, a
k + 1
] =
即
m
k
= a
1
a
2
a
k
，
(m
k
,a
k1
)
m
k
a
k1
= a
1
a
2
a
k
a
k + 1
，
(m
k
,a
k1
)
18
显然m
k
a
1
a
2
a
k
，(m
k
, a
k + 1
) 1。所以若使上式成立，必是
(m
k
, a
k + 1
) = 1， (5)
并且
m
k
= a
1
a
2
a
k
。 (6)
由式(6)与式(5)推出
(a
i
, a
k + 1
) = 1，1 i k； (7)
由式(6)及归纳假设推出
(a
i
, a
j
) = 1，1 i, j k，i j
。 (8)
综合式(7)与式(8)，可知当n = k 1时，充分性成立。由归纳法证明了
充分性。证毕。
定理4有许多应用。例如，如果m
1
, m
2
, , m
k
是两两互素的整数，
那么，要证明m = m
1
m
2
m
k
整除某个整数Q，只需证明对于每个i，1
i k，都有m
i
Q。这一点在实际计算中是很有用的。对于函数f(x)，
要验证命题“mf(n)，nZ”是否成立，可以用第二节例5中的方法，
验证“mf(r)，r = 0, 1, , m 1”是否成立。这需要做m次除法。但
是，若分别验证“m
i
f(r
i
)，r
i
= 0, 1, , m
i
1，1 i k”是否成立，
则总共需要做m
1
m
2
m
k
次除法。后者的运算次数显然少于前
者。
例1 设a，b，c是正整数，证明：[a, b, c](ab, bc, ca) = abc
。
解 由定理3和定理2有
[a,b]c
[a, b, c] = [[a, b], c] =， (9)
([a,b],c)
由第三节定理5和定理2的推论，
(ab, bc, ca) = (ab, (bc, ca)) = (ab, c(a, b))
abc
)
(ab[a,b],abc)
ab([a,b],c)
。 (10) =
(
ab,
[a,b][a,b][a,b]
联合式(9)与式(10)得到所需结论。
例2 对于任意的整数a
1
, a
2
, , a
n
及整数k，1 k n，证明：
[a
1
, a
2
, , a
n
] = [[a
1
, , a
k
],[a
k + 1
, , a
n
]]
19
解 因为[a
1
, a
2
, , a
n
]是a
1
, , a
k
, a
k + 1
, , a
n
的公倍数，所以由
定理2推论，推出
[a
1
, , a
k
][a
1
, a
2
, , a
n
]，
[a
k + 1
, , a
n
][a
1
, a
2
, , a
n
]，
再由定理3推论知
[[a
1
, , a
k
], [a
k + 1
, , a
n
]][a
1
, a
2
, , a
n
]。 (11)
另一方面，对于任意的a
i
（1 i n），显然
a
i
[[a
1
, , a
k
], [a
k + 1
, , a
n
]]，
所以由定理3推论可知
[a
1
, a
2
, , a
n
][[a
1
, , a
k
], [a
k + 1
, , a
n
]]，
联合上式与式(11)得证。
例3 设a，b，c是正整数，证明：
[a, b, c][ab, bc, ca] = [a, b][b, c][c, a]。
解 由定理2推论2及例2，有
[a, b, c][ab, bc, ca] = [[a, b, c]ab, [a, b, c]bc, [a, b, c]ca]
= [[a
2
b, ab
2
, abc], [abc, b
2
c, bc
2
], [a
2
c, abc, ac
2
]]
= [a
2
b, ab
2
, abc, abc, b
2
c, bc
2
, a
2
c, abc, ac
2
]
= [abc, a
2
b, a
2
c, b
2
c, b
2
a, c
2
a, c
2
b]
以及
[a, b][b, c][c, a] = [[a, b]b, [a, b]c][c, a]
= [ab, b
2
, ac, bc][c, a]
= [ab[c, a], b
2
[c, a], ac[c, a], bc[c, a]]
= [abc, a
2
b, b
2
c, b
2
a, ac
2
, a
2
c, bc
2
, bca]
= [abc, a
2
b, a
2
c, b
2
c, b
2
a, c
2
a, c
2
b]，
由此得证。
习 题 四
1. 证明定理1。
2. 证明定理3的推论。
3. 设a，b是正整数，证明：(a b)[a, b] = a[b, a b]。
20
4. 求正整数a，b，使得a b = 120，(a, b) = 24，[a, b] = 144。
5. 设a，b，c是正整数，证明：
[a,b,c]
2
(a,b,c)
2
。
[a,b][b,c][c,a](a,b)(b,c)(c,a)
6. 设k是正奇数，证明：1 2 91
k
2
k
9
k
。
第五节 辗转相除法
本节要介绍一个计算最大公约数的算法——辗转相除法，又称
Euclid算法。它是数论中的一个重要方法，在其他数学分支中也有广
泛的应用。
定义1 下面的一组带余数除法，称为辗转相除法。
设a和b是整数，b 0，依次做带余数除法：
a = bq
1
r
1
，
0 < r
1
< |b|，
b = r
1
q
2
r
2
，
0 < r
2
< r
1
，
r
k 1
= r
k
q
k + 1
r
k + 1
，0 < r
k + 1
< r
k
， (1)
r
n 2
= r
n 1
q
n
r
n
， 0 < r
n
< r
n-1
，
r
n 1
= r
n
q
n + 1
。
由于b是固定的，而且
|b| > r
1
> r
2
> ，
所以式(1)中只包含有限个等式。
下面，我们要对式(1)所包含的等式的个数，即要做的带余数除法
的次数进行估计。
引理1 用下面的方式定义Fibonacci数列{F
n
}：
F
1
= F
2
= 1，F
n
= F
n 1
F
n 2
，n 3，
那么对于任意的整数n 3，有
F
n
>
n
2
， (2)
21
其中
=
15
。
2
证明 容易验证
2
=
1。
当n = 3时，由
F
3
= 2 >
15
=
2
可知式(2)成立。
假设式(2)对于所有的整数k n（n 3）成立，即
F
k
>
k
2
，k n，
则
F
n + 1
= F
n
F
n 1
>
n
2
n
3
=
n
3
(
1) =
n
3
2
=
n
1
，
即当k = n 1时式(2)也成立。由归纳法知式(2)对一切n 3成立。证
毕。
定理1(Lame) 设a, bN，a > b，使用在式(1)中的记号，则
n < 5log
10
b。
证明 在式(1)中，r
n
1，q
n + 1
2，q
i
1（1 i n），因此
r
n
1 = F
2
，
r
n 1
2r
n
2 = F
3
，
r
n 2
r
n 1
r
n
F
3
F
2
= F
4
，
b r
1
r
2
F
n + 1
F
n
= F
n + 2
，
由此及式(2)得
15
n
b
n
=
()
，
2
即
log
10
b nlog
10
151
n
，
25
这就是定理结论。证毕。
定理2 使用式(1)中的记号，记
P
0
= 1，P
1
= q
1
，P
k
= q
k
P
k 1
P
k 2
，k 2，
22
Q
0
= 0，Q
1
= 1，Q
k
= q
k
Q
k 1
Q
k 2
，k 2，
则
aQ
k
bP
k
= (1)
k
1
r
k
，k = 1, 2, , n 。 (3)
证明 当k = 1时，式(3)成立。
当k = 2时，有
Q
2
= q
2
Q
1
Q
0
= q
2
，P
2
= q
2
P
1
P
0
= q
2
q
1
1，
此时由式(1)得到
aQ
2
bP
2
= aq
2
b(q
2
q
1
1) = (a bq
1
)q
2
b = r
1
q
2
b = r
2
，
即式(3)成立。
假设对于k < m（1 m n）式(3)成立，由此假设及式(1)得到
aQ
m
bP
m
= a(q
m
Q
m 1
Q
m 2
) b(q
m
P
m 1
P
m 2
)
= (aQ
m 1
bP
m 1
)q
m
(aQ
m 2
bP
m 2
)
= (1)
m
2
r
m 1
q
m
(1)
m
3
r
m 2
= (1)
m
1
(r
m 2
r
m 1
q
m
) = (1)
m
1
r
m
，
即式(3)当k = m时也成立。定理由归纳法得证。证毕。
定理3 使用式(1)中的记号，有r
n
= (a, b)。
证明 由第三节定理1，从式(1)可见
r
n
= (r
n 1
, r
n
) = (r
n 2
, r
n 1
) = = (r
1
, r
2
) = (b, r
1
) = (a, b)。
证毕。
现在我们已经知道，利用辗转相除法可以求出整数x，y，使得
ax by = (a, b)
。 (4)
为此所需要的除法次数是O(log
10
b)。但是如果只需要计算(a, b)而不需
要求出使式(4)成立的整数x与y，则所需要的除法次数还可更少一些。
例1 设a和b是正整数，那么只使用被2除的除法运算和减法
运算就可以计算出(a, b)。
解 下面的四个基本事实给出了证明：
(ⅰ) 若ab，则(a, b) = a；
|
a
1
，b2
b
1
，2
|
b
1
，
1，则 (ⅱ) 若a = 2
a
1
，
2
(a, b) = 2
(2
a
1
, b
1
)；
|
a，b2
b
1
，2
|
b
1
，则(a, b) = (a, b
1
)； (ⅲ) 若
2
ab
(ⅳ) 若
2
|
a，2
|
b，则(a,b)
(||
,b
)
。
2
23
在实际计算过程中，若再灵活运用最大公约数的性质（例如第三
节定理4的推论），则可使得求最大公约数的过程更为简单。
例2 用辗转相除法求(125, 17)，以及x，y，使得
125x 17y = (125, 17)。
解 做辗转相除法：
125 = 717 6，q
1
= 7，r
1
= 6，
17 = 26 5， q
2
= 2，r
2
= 5，
6 = 15 1， q
3
= 1，r
3
= 1，
5 = 51， q
4
= 5。
由定理4，(125, 17) = r
3
= 1。
利用定理2计算（n = 3）
P
0
= 1，P
1
= 7，P
2
= 27 1 = 15，P
3
= 115 7 = 22，
Q
0
= 0，Q
1
= 1，Q
2
= 21 0 = 2，Q
3
= 12 1 = 3，
取x = (1)
3 1
Q
3
= 3，y = (1)
3
P
3
= 22，则
1253 17(22) = (125, 17) = 1。
例3 求(12345, 678)。
解 (12345, 678) = (12345, 339) = (12006, 339) = (6003, 339)
= (5664, 339) = (177, 339) = (177, 162) = (177, 81)
= (96, 81) = (3, 81) = 3。
例4 在m个盒子中放若干个硬币，然后以下述方式往这些盒子
里继续放硬币：每一次在n（n < m）个盒子中各放一个硬币。证明：
若(m, n) = 1，那么无论开始时每个盒子中有多少硬币，经过若干次放
硬币后，总可使所有盒子含有同样数量的硬币。
解 由于(m, n) = 1，所以存在整数x，y，使得mx ny = 1。因此
对于任意的自然数k，有
1 m(x kn) = n(km y)，
这样，当k充分大时，总可找出正整数x
0
，y
0
，使得
1 mx
0
= ny
0
。
上式说明，如果放y
0
次（每次放n个），那么在使m个盒子中各放x
0
个后，还多出一个硬币。把这个硬币放入含硬币最少的盒子中（这是
可以做到的），就使它与含有最多硬币的盒子所含硬币数量之差减少1。
因此经过若干次放硬币后，必可使所有盒子中的硬币数目相同。
24
习 题 五
1. 说明例1证明中所用到的四个事实的依据。
2. 用辗转相除法求整数x，y，使得1387x 162y = (1387, 162)。
3. 计算：(27090, 21672, 11352)。
4. 使用引理1中的记号，证明：(F
n + 1
, F
n
) = 1。
5. 若四个整数2836，4582，5164，6522被同一个大于1的整数
除所得的余数相同，且不等于零，求除数和余数各是多少？
6. 记M
n
= 2
n
1，证明：对于正整数a，b，有(M
a
, M
b
) = M
(a, b)
。
第六节 算术基本定理
在本节中，我们要介绍整数与素数的一个重要关系，即任何大于
1的正整数都可以表示成素数的乘积。
引理1 任何大于1的正整数n可以写成素数之积，即
n = p
1
p
2
p
m
， (1)
其中p
i
（1 i m）是素数。
证明 当n = 2时，结论显然成立。
假设对于2 n k，式(1)成立，我们来证明式(1)对于n = k 1也
成立，从而由归纳法推出式(1)对任何大于1的整数n成立。
如果k 1是素数，式(1)显然成立。
如果k 1是合数，则存在素数p与整数d，使得k 1 = pd。由于
2 d k，由归纳假定知存在素数q
1
, q
2
, , q
l
，使得d = q
1
q
2
q
l
，从
而k 1 = pq
1
q
2
q
l
。证毕。
定理1(算术基本定理) 任何大于1的整数n可以唯一地表示成
1
2
k
p
2
p
n =
p
1k
， (2)
其中p
1
, p
2
, , p
k
是素数，p
1
< p
2
< < p
k
，
1
,
2
, ,
k
是正整数。
证明 由引理1，任何大于1的整数n可以表示成式(2)的形式，
因此，只需证明表示式(2)的唯一性。
假设p
i
（1 i k）与q
j
（1 j l）都是素数，
25
p
1
p
2
p
k
，q
1
q
2
q
l
， (3)
并且
n = p
1
p
2
p
k
= q
1
q
2
q
l
， (4)
则由第三节定理4推论1，必有某个q
j
（1 j l），使得p
1
q
j
，所以
p
1
= q
j
；又有某个p
i
（1 i k），使得q
1
p
i
，所以q
1
= p
i
。于是，由式
(3)可知p
1
= q
1
，从而由式(4)得到
p
2
p
k
= q
2
q
l
。
重复上述这一过程，得到
k = l，p
i
= q
i
，1 i k
。
证毕。
定义1 使用定理1中的记号，称
1
2
k
p
2
p
n =
p
1
k
是n的标准分解式，其中p
i
（1 i k）是素数，p
1
< p
2
< < p
k
，
i
（1 i k）是正整数。
推论1 使用式(2)中的记号，有
(ⅰ) n的正因数d必有形式
k
1
2
p
2
p
k
d =
p
1
，
i
Z，0
i
i
，1 i k；
(ⅱ) n的正倍数m必有形式
k
2
p
k
m =
p
1
1
p
2
M，MN，
i
N，
i
i
，1 i k。
证明 留作习题。
推论2 设正整数a与b的标准分解式是
l
k
1
1
1
1
s
k
ap
1
p
k
q
1
q
l
，bp
1
p
k
r
1
r
s
，
其中p
i
（1 i k），q
i
（1 i l）与r
i
（1 i s）是两两不相同的素
数，
i
，
i
（1 i k），
i
（1 i l）与
i
（1 i s）都是非负整数，
则
(a, b) =
p
1
1
p
k
k
，
i
= min{
i
,
i
}，1 i k，
[a, b] =
p
1
1
p
k
k
q
1
1
q
l
l
r
1
1
r
s
s
，
i
= max{
i
,
i
}，1 i k。
证明 留作习题。
为了方便，推论2常叙述为下面的形式：
26
推论2
设正整数a与b的标准分解式是
k
1
2
1
1
k
ap
1
p
2
p
k
，bp
1
p
2
p
k
，
其中p
1
, p
2
, , p
k
是互不相同的素数，
i
，
（都是非负整数，
i
1 i k）
则
k
1
1
(a,b)p
1
p
2
p
k
，
i
min{
i
,
i
}，1ik，
k
1
1
[a,b]p
1
p
2
p
k
，
i
max{
i
,
i
}，1ik。
推论3 设a，b，c，n是正整数，
ab = c
n
，(a, b) = 1， (5)
则存在正整数u，v，使得
a = u
n
，b = v
n
，c = uv，(u, v) = 1。
k
1
1
p
2
p
k
证明 设c =
p
1
，其中p
1
, p
2
, , p
k
是互不相同的素数，
i
（1 i k）是正整数。又设
k
1
2
1
1
k
ap
1
p
2
p
k
，bp
1
p
2
p
k
，
其中
I
，
i
（1 i k）都是非负整数。由式(5)及推论2
可知
min{
i
,
i
} = 0，
i
i
= n
i
，1 i k，
因此，对于每个i（1 i k），等式
i
= n
i
，
i
= 0与
i
= 0，
i
= n
i
有且只有一个成立。这就证明了推论。证毕。
例1 写出51480的标准分解式。
解 我们有
51480 = 225740 = 2
2
12870 = 2
3
6435
= 2
3
51287 = 2
3
53429
= 2
3
53
2
143 = 2
3
3
2
51113。
例2 设a，b，c是整数，证明：
(ⅰ) (a, b)[a, b] = ab；
(ⅱ) (a, [b, c]) = [(a, b), (a, c)]。
解 为了叙述方便，不妨假定a，b，c是正整数。
(ⅰ) 设
k
1
2
1
1
k
ap
1
p
2
p
k
，bp
1
p
2
p
k
，
其中p
1
, p
2
, , p
k
是互不相同的素数，
i
，
i
（1 i k）都是非负整数。
27
由定理1推论2
，有
k
1
1
(a,b)p
1
p
2
p
k
，
i
min{
i
,
i
}，1ik，
k
1
1
[a,b]p
1
p
2
p
k
，
i
max{
i
,
i
}，1ik。
由此知
(a, b)[a, b] =
p
i
i1
k
i
i
i1
k
i
,
i
}
p
i
min{
i
,
i
}max{
p
i
i
i
=ab；
i1
k
(ⅱ) 设
a
p
i
，b
p
i
，c
p
i
i
，
i1i1i1
k
i
k
i
k
其中p
1
, p
2
, , p
k
是互不相同的素数，
i
，
i
，
i
（1 i k）都是非负
整数。由定理1推论2
，有
(a,[b,c])
p
i
i
，[(a,b),(a,c)]
p
i
i
，
i1i1
kk
其中，对于1 i k，有
i
= min{
i
, max{
i
,
i
}}，
i
= max{min{
i
,
i
}, min{
i
,
i
}}，
不妨设
i
i
，则
min{
i
,
i
} min{
i
,
i
}，
所以
i
= min{
i
,
i
} =
i
，
即(a, [b, c]) = [(a, b), (a, c)]。
注：利用定理1可以容易地处理许多像例2这样的问题。
111
例3 证明：
N1
（n 2）不是整数。
352n1
解 设
3
k
2n 1 < 3
k
+ 1
。
对于任意的1 i n，2i 1 3
k
，记
2i 1 =
3
i
Q
i
，Q
i
Z，
由第一节例5，知
i
k 1。因为3
k
1
Q
1
Q
2
Q
2n 1
是整数，所以，如
果N是整数，则存在整数Q，使得
28
3
由于3
|
Q
1
Q
2
Q
2n1
，所以上式右端不是整数，这个矛盾说明N不能
是整数。
3
k
1
Q
1
Q
2
Q
2n 1
N = Q 3
k
1
Q
1
Q
2
Q
2n 1
1
k
。
习 题 六
1. 证明定理1的推论1。
2. 证明定理1的推论2。
3. 写出22345680的标准分解式。
4. 证明：在1, 2, , 2n中任取n 1数，其中至少有一个能被另
一个整除。
11
（n 2）不是整数。
2n
6. 设a，b是正整数，证明：存在a
1
，a
2
，b
1
，b
2
，使得
a = a
1
a
2
，b = b
1
b
2
，(a
2
, b
2
) = 1，
并且[a, b] = a
2
b
2
。
5. 证明：
1
第七节 函数[x]与{x}
本节中要介绍函数[x]，它在许多数学问题中有广泛的应用。
定义1 设x是实数，以[x]表示不超过x的最大整数，称它为x
的整数部分，又称{x} = x [x]为x的小数部分。
定理1 设x与y是实数，则
(ⅰ) x y [x] [y]；
(ⅱ) 若m是整数，则[m x] = m [x]；
(ⅲ) 若0 x < 1，则[x] = 0；
若{x}{y}1
[x][y]
(ⅳ) [x y] =
；
[x][y]1若{x}{y}1
29
[x]
(ⅴ) [x] =
[x]1
0
(ⅵ) {x} =
1{x}
若xZ
若xZ
若xZ
若xZ
；
。
证明 留作习题。
定理2 设a与b是正整数，则在1, 2, , a中能被b整除的整数
有
[
a
]
个。
b
证明 能被b整除的正整数是b, 2b, 3b, ，因此，若数1, 2, , a
kb a < (k 1)b k
中能被b整除的整数有k个，则
a
a
< k 1 k =
[]
。
b
b
证毕。
由定理2我们看到，若b是正整数，那么对于任意的整数a，有
aa
ab
[]
b
{}
，
bb
即在带余数除法
a = bq r，0 r < b
aa
中有
q
[]
，rb
{}
。
bb
1
2
k
p
2
p
定理3 设n是正整数，n! =
p
1
则
k
是n!的标准分解式，
i
=
[
r1
n
p
i
r
]
。 (1)
证明 对于任意固定的素数p，以p(k)表示在k的标准分解式中的
p的指数，则
p(n!) = p(1) p(2) p(n)。
以n
j
表示p(1), p(2), , p(n)中等于j的个数，那么
p(n!) = 1n
1
2n
2
3n
3
， (2)
显然，n
j
就是在1, 2, , n中满足p
j
a并且p
j
+ 1
|
a的整数a的个
30
数，所以，由定理2有
n
j
=
[
n
p
]
[
j
n
p
j1
]
。
将上式代入式(2)，得到
nnnnnn
p(n!)1
([]
[
2
])
2
([
2
]
[
3
])
3
([
3
]
[
4
])
p
ppppp
[
r1
n
p
r
]
。
即式(1)成立。证毕。
推论 设n是正整数，则
n! =
p
r1
pn
pn
[
p
r
]
n
，
其中
表示对不超过n的所有素数p求积。
定理４ 设n是正整数，1 k n 1，则
n!
N。 (3)
C
k
n
k!(nk)!
若n是素数，则n
C
k
n
，1 k n 1。
证明 由定理3，对于任意的素数p，整数n!，k!与(n k)!的标准
分解式中所含的p的指数分别是
nknk
[]
，
[]
与
r
r
[
r
]
。
p
r1
p
r1
p
r1
利用定理1可知
nknk
[
r
]
[
r
]
[
r
]
，
p
r1
p
r1
p
r1
因此
C
k
n
是整数。
若n是素数，则对于1 k n 1，有
(n, k!) = 1，(n, (n k)!) = 1 (n, k!(n k)!) = 1，
由此及
31
C
k
n
n(n1)!
N，
k!(nk)!
推出k!(n k)!(n 1)!，从而n
C
k
n
。证毕。
例1 求最大的正整数k，使得10
k
199!。
解 由定理3，199!的标准分解式中所含的5的幂指数是
199
[
199
]
[
199
]
[]
= 47，
5
5
2
5
3
所以，所求的最大整数是k = 47。
例2 设x与y是实数，则
[2x] [2y] [x] [x y] [y]。 (4)
解 设x = [x]
，0
< 1，y = [y]
，0
< 1，则
[x] [x y] [y] = 2[x] 2[y] [
]， (5)
[2x] [2y] = 2[x] 2[y] [2
] [2
]。 (6)
如果[
] = 0，那么显然有[
] [2
] [2
]；
1
如果[
] = 1，那么
与
中至少有一个不小于，于是
2
[2
] [2
] 1 = [
]。
因此无论[
] = 0或1，都有[
] [2
] [2
]，由此及式(5)和式
(6)可以推出式(4)。
例3 设n是正整数，则
[nn1][4n2]
。 (7)
解 首先，我们有
[nn1]nn12n12n(n1)
2n12n14n2，
所以
[nn1][4n2]
。
若上式中的等号不成立，即
[nn1][4n2]
， (8)
则存在整数a，使得
[nn1]a[4n2]
，
32
因此
2n12n(n1)a
2
4n2，
22
2nna2n12n1，
(2n 1)
2
1< (a
2
2n 1)
2
(2n 1)
2
，
所以
a
2
2n 1 = 2n 1 a
2
= 4n 2。 (9)
但是，无论2a或2
|
a，式(9)都不能成立，这个矛盾说明式(8)不能成
立，即式(7)成立。
例4 设x是正数，n是正整数，则
12n1
[x]
[
x
]
[
x
]
[
x
]
= [nx]。
nnn
ii1
解 设x = [x]
，
，0 i n 1，则
nn
12n1
[x]
[
x
]
[
x
]
[
x
]
nnn
= n[x] i = n[x] [n
] = [n([x]
)] = [nx]。
例5 求[
(32)
1992
]的个位数。
解 由
(32)
2
526
得
(32)
1992
(32)
1992
9962
C
996
5
994
2
2
62
996
6
498
)
996996
=
(526)(526)
=
2(5
= 10A 2
997
6
498
= 10A 224
498
= 10A 2(25 1)
498
= 10B 2， （10）
其中A和B都是整数。由于0 < 5
26
< 1，所以，由式(10)可知
[
(32)
1996
]的个位数是1。
注：一般地，如果A，BN，A
2
> B，
AB
< 1，则由
k2
(A
B)
k
(A
B)
k
2(A
k
C
2
B
)
k
A
可以求出[
(AB)
k
]。
33
例6 设x和y是正无理数，
11
1
，证明：数列
xy
[x], [2x], , [kx], 与 [y], [2y], , [my], (11)
联合构成了整个正整数集合，而且，两个数列中的数互不相同。
解 显然x > 1，y > 1，并且x y。因此，在数列(11)中至多有一
个数等于给定的正整数n，否则存在正整数k与m，使得
n = [kx] = [my]。
因为x与y都是无理数，所以我们有
n < kx < n 1，n < my < n 1，
k1km1m
，，
n1xnn1yn
km11km
1，
n1xyn
n < k m < n 1，
这是不可能的。
下面证明，对于任意给定的正整数n，总可找到某个正整数k，使
得n等于[kx]或者[ky]。假设不然，则存在p, qN，使得
[px] < n < [(p 1)x]，[qy] < n < [(q 1)y]。
于是（因为x和y是无理数），
px < n < n 1 [(p 1)x] < (p 1)x，
qy < n < n 1 [(q 1)y] < (q 1)y，
pq11pq2
，
1
nxyn1
p q < n < n 1 < p q 2，
这是不可能的。
习 题 七
1. 证明定理1。
2. 求使12347!被35
k
整除的最大的k值。
34
n2
r1
]
= n。 3. 设n是正整数，x是实数，证明：
[
r
2
r1
4. 设n是正整数，求方程
x
2
[x
2
] = (x [x])
2
在[1, n]中的解的个数。
5. 证明：方程
f(x) = [x] [2x] [2
2
x] [2
3
x] [2
4
x] [2
5
x] = 12345
没有实数解。
6. 证明：在n!的标准分解式中，2的指数h = n k，其中k是n
的二进制表示的位数码之和。
第八节 素 数
在第六节中我们已经证明了：每个正整数可以表示成素数幂的乘
积。这就引出了一个问题：素数是否有无穷多个？如果有无穷多个，
那么，作为无穷大量，素数个数具有怎样的性状？这是数论研究中的
一个中心课题。本节要对这一问题作初步的研究。
定义1 对于正实数x，以
(x)表示不超过x的素数个数。
例如，
(15) = 6，
(10.4) = 4，
(50) = 15。
定理1 素数有无限多个。
证明 我们给出三个证明方法。
证法Ⅰ 假设只有k个素数，设它们是p
1
, p
2
, , p
k
。记
N = p
1
p
2
p
k
1。
由第一节定理2可知，N有素因数p，我们要说明p p
i
，1 i k，
从而得出矛盾。
事实上，若有某个i，1 i k，使得p = p
i
，则由
pN = p
1
p
2
p
k
1
推出p1，这是不可能的。因此在p
1
, p
2
, , p
k
之外又有一个素数p，
这与假设是矛盾的。所以素数不可能是有限个。
证法Ⅱ 我们证明整数
35
2
1，2
2
1，2
2
1，，2
2
1，
2n
是两两互素的，从而由第六节引理1可知素数有无限多个。
事实上，若m和n是整数，m > n 0，则
2
2
1(2
2
(2
2
(2
2
mm1
1)(2
2
1)(2
2
m1
1)
1)(2
2
m2m1m2
1)
mn1
1)(2
2
m2
1)
(2
2
1)(2
2
1)
nn
Q(2
2
1)，
n
此处Q是整数。因此
2
2
1Q(2
2
1)2，
mn
故
(2
2
1,2
2
1)(2,2
2
1)1。
mnn
证法Ⅲ 假设只有有限个素数p
1
, p
2
, , p
k
。由第六节定理1，每
个正整数可以写成
1
2
p
2
p
k
k
，
i
1，1 i k。 n =
p
1
由于
(
1
1
)
1
1
p
p
，
0
所以，对于任何正整数N，有
11111
1
1
(
1
)
1
(
1
)
(
1
1
)
1
。
23Np
1
p
2
p
k
当N 时，上式左端是一个无穷大量，右端是有限的，这个矛盾说
明素数不能是有限多个。证毕。
注1：形如
2
2
1
（n = 0, 1, 2, ）的数称为Fermat数。Fermat
曾经猜测它们都是素数。这是错误的，因为尽管F
0
，F
1
，F
2
，F
3
，F
4
都是素数，F
5
=
2
2
16416700417
却是合数。
注2：将全体素数按大小顺序排列为
p
1
= 2，p
2
= 3，p
3
= 5，p
4
，，p
n
，，
36
5
n
那么由第一个证明方法可以看出
p
n + 1
p
1
p
2
p
n
1，n 1。
定理2 对于n 1，
1
(ⅰ)
(n) log
2
n；
2
n
2
(ⅱ) p
n
2。
证明 (ⅰ) 设n是大于1的正整数。由算术基本定理，对于任
意的整数k，1 k n，都有整数a和b，使得k = a
2
b，其中整数b不
能被任何大于1的整数的平方整除。现在，我们来看使得
k = a
2
b，1 k n (1)
即1 a
2
b n成立的整数a，b有多少对。首先，整数a的个数
n
；
其次，由于b n并且不含有平方因数，所以，整数b的因数只可能是
不超过n的不同的素数的乘积，因此，整数b的个数 2
(
n
)
。这样，
使得式(1)成立的整数a和b至多是
n
2
(
n
)
对，所以，n
n
2
(
n
)
，即
1
(n) log
2
n。
2
(ⅱ) 以p
m
表示第m个素数，在结论(ⅰ)中取n = p
m
，我们得到m
1
log
2
p
m
，由此即可得到结论(ⅱ)。证毕。
2
注：定理2对于无穷大量
(x)的下界估计是相当粗糙的。下面的
定理是已经知道的（由于其证明较繁，故本书中不予证明）。
定理3(素数定理) 我们有
x
(x) ，（x），
logx
此处logx是以e为底的x的对数。
推论 以p
n
表示第n个素数，则
p
n
nlogn（n）。
证明 由定理3，当n 时，有
p
n
n 。 (2)
logp
n
因此
37
nlogp
n
p
n
，
logn loglogp
n
logp
n
，
logn logp
n
。
由上式与式(2)得p
n
nlogn（n）。证毕。
例1 若a > 1，a
n
1是素数，则a = 2，并且n是素数。
解 若a > 2，则由
a
n
1 = (a 1)(a
n
1
a
n
2
1)
可知a
n
1是合数。所以a = 2。
若n是合数，则n = xy，x > 1，y > 1，于是由
2
xy
1 = (2
x
1)(2
x
(
y
1)
2
x
(
y
2)
1)
以及2
x
1 > 1可知2
n
1是合数，所以2
n
1是素数时，n必是素数。
n
注：若n是素数，则称2 1是Mersenne数。
例2 形如4n 3的素数有无限多个。
解 若不然，假设只有k个形如4n 3的素数p
1
, p
2
, , p
k
。记
N = 4p
1
pp
k
– 1。
由第六节引理1，正整数N可以写成若干个素数之积。我们指出，
这些素因数中至少有一个是4n 3形式。否则，若它们都是4n 1的
形式，则N也是4n 1的形式，这与N的定义矛盾。以p表示这个素
因数，则p p
i
，1 i k。否则若有某个i，1 i k，使得p = p
i
，则
由pN推出p1，这是不可能的。因此在p
1
, p
2
, , p
k
之外又存在一个
形如4n 3的素数p，这与原假设矛盾，所以形如4n 3的素数有无
限多个。
例3 设f(x) = a
k
x
k
a
k 1
x
k
1
a
0
是整系数多项式，那么，
存在无穷多个正整数n，使得f(n)是合数。
解 不妨假定a
k
> 0。于是f(x) （x ），因此，存在正整
数N，使得当n > N时，有f(n) > 1。取整数x > N，记
y = f(x) = a
k
x
k
a
k 1
x
k
1
a
0
，
又设r是任意的正整数，n = ry x，则
f(n) = f(ry x) = a
k
(ry x)
k
a
k 1
(ry x)
k
1
a
0
= yQ f(x) = y(Q 1)
38
是合数。
习 题 八
1. 证明：若2
n
1是素数，则n是2的乘幂。
2. 证明：若2
n
1是素数，则n是素数。
3. 证明：形如6n 5的素数有无限多个。
4. 设d 是正整数，6
|
d，证明：在以d为公差的等差数列中，
连续三项都是素数的情况最多发生一次。
5. 证明：对于任意给定的正整数n，必存在连续的n个自然数，
使得它们都是合数。
1
6. 证明：级数
发散，此处使用了定理1注2中的记号。
n1
p
n
39