初等数论第一章整除理论
藕粉的做法-以珍惜为话题的作文
* *
第一章 整除理论
整除性理论是初等数论的基础。本章要介绍带余数除法，辗转相除法，最大公约数，最小公
倍数，算术基本定理以及它们的一些应用。
第一节 数的整除性
定义1
设
a
，
b
是整数，
b
0，如果存在
整数
c
，使得
a
=
bc
成立，则称
a
被
b
整除，
a
是
b
的倍
数，
b
是
a
的约数（因数或除数），并且使用记号
b
a
；如
果不存在整数
c
使得
a
=
bc
成立，则称
a
不被
|
a
。
b
整除，记为
b
显然每个非零整数
a
都有约数
1，
a
，称
* *
这四个数为
a
的平
凡约数，
a
的另外的约数称为
非平凡约数。
被2整除的整数称为偶数，不被2整除的
整数称为奇数。
定理1
下面的结论成立：
(ⅰ)
a
b
a
b
；
(ⅱ)
a
b
，
b
c
a
c
；
(ⅲ)
b
a
i
，
i
= 1, 2, ,
k
b
a
1
x
1
a
2
x
2
a
k
x
k
，此处
x
i
（
i
= 1, 2, ,
k
）是任
意的整数；
(ⅳ)
b
a
bc
ac
，此处
c
是任意的非
零整数；
(ⅴ)
b
a
，
a
0
|
b
|
|
a
|；
b
a
且|
a
| <
|
b
|
a
= 0。
证明 留作习题。
* *
定义2 若整数
a
0，1，并且只有约数
1和
a
，则称
a
是素数（或质数）；否则称
a
为合数。
以后在本书中若无特别说明，素数总是指正
素数。
定理2
任何大于1的整数
a
都至少有一个
素约数。
证明
若
a
是素数，则定理是显然的。
若
a
不是素数，那么它有两个以上
的正的非
平凡约数，设它们是
d
1
,
d
2
,
,
d
k
。不妨设
d
1
是其中最小的。若
d<
br>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
，则
2
s
= 2 (2
r
n
r
) (3
r
(
n
1)
r
) (
n
r
2
r
) = 2 (
n
2)
Q
，
其中
Q
是整数。若
n
2
s
，由上式知
n
22，
* *
因为
n
2 > 2，这是不可能的，所以
n
2
|
s
。
例2 设
A
= {
d
1
,
d
2
, ,
d
k
}是
n
的所有
约数的集合，则
B
=
{
nnn
,,
,
}
d
1<
br>d
2
d
k
也是
n
的所有约数的集合。
解
由以下三点理由可以证得结论：
(ⅰ)
A
和
B
的元素个数相同；
(ⅱ) 若
d
i
A
，即
d
i
n
，则
然；
(ⅲ) 若
d
i
d
j
，则
nn
。
d
i
dj
n
|
n
，反之亦
d
i
例3 以
d
(
n
)表示
n
的正约数的个数，例
如：
d
(1) = 1，
d
(2) = 2，
d
(3) =
2，
d
(4) = 3，
。问：
*
*
d
(1)
d
(2)
d
(1997)
是否为偶数？
解
对于
n
的每个约数
d
，都有
n
=
d
因此，
n
的正约数
d
与
n
，
d
n
是成对地出现的。只
d
nn
有当
d
=，即
n
=
d
2
时，
d
和才是同一个
dd
数。故当且仅当
n
是完全平方数时，
d
(
n<
br>)是奇数。
因为44
2
< 1997 <
45
2
，所以在
d
(1),
d
(2),
,
d
(1997)中恰有44个奇数，故
d
(1)
d
(2)
d
(1997)是偶数。
例4
设凸2
n
边形
M
的顶点是
A
1
,
A
2
, ,
A
2
n
，点
O
在
M
的内部，用1, 2,
, 2
n
将
M
的
2
n
条边分别编号，又将
OA
1
,
OA
2
, ,
OA
2
n
也
同样进行编号，若把这些编号作为相应的线段的
长度，证明：无论怎么编号，都不能
使得三角形
OA
1
A
2
,
OA
2
A
3
, ,
OA
2
n
A
1
的周长都相等。
*
*
解 假设这些三角形的周长都相等，记为
s
。
则
2
ns
= 3(1 2 2
n
) =
3
n
(2
n
1)，
即
2
s
=
3(2
n
1)，
因此23(2
n
1)，这是不可能的，这个矛盾说
明这些三角形的周长不可能全都相等。
例5
设整数
k
1，证明：
(ⅰ) 若2
k
n
< 2
k
1
，1
a
n
，
a
2
k
，
|
a
；
则2
k
(ⅱ) 若3
k
2
n
1 < 3
k
+ 1
，1
b
n
，
|
2
b
1。
2
b
1
3
k
，则3
k
解 (ⅰ)
若2
k
|
a，
则存在整数
q
，使得
a=
q
2
k
。显然
q
只可能是0或1。此时
a=
0或2
k
，
|
a
；
这都是不可能的，所以2
k
* *
(ⅱ) 若
3
k
|2b-1，则存在整数
q
，使得
2b-1
=
q
3
k
，显然
q
只可能是0，1,
或2。此时
2b-1
=
0，3
k
，或
23
，这
都是不可能的，所
k
以3
k
|
2
b
1。
例6 写出不超过100的所有的素数。
解
将不超过100的正整数排列如下：
1 2 3 4 5 6
7
8 9 10
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中所使用的寻找素数的方法，称为
* *
Eratosthe
nes筛法。它可以用来求出不超过任
何固定整数的所有素数。在理论上这是可行的；
但在实际
应用中，这种列出素数的方法需要大量
的计算时间，是不可取的。
例7
证明：存在无穷多个正整数
a
，使得
n
4
a
（
n
= 1, 2, 3, ）
都是合数。
解
取
a
= 4
k
4
，对于任意的
n
N，有
n
4
4
k
4
= (
n
2
2
k
2
)
2
4
n
2
k
2
= (
n
2
2
k
2
2
nk
)(
n
2
2
k
2
2
nk
)。
因为
n
2
2
k
2
2
nk
=
(
n
k
)
2
k
2
k
2
，
所以，对于任意的
k
= 2, 3,
以及任意的
n
N，
n
4
a
是合数。
例8 设
a
1
,
a
2
, ,
a
n
是整数，且
* *
a
1
a
2
a
n
=
0，
a
1
a
2
a
n
=
n
，
则4
n
。
解
如果2
|
n
，则
n
,
a
1
,
a
2
, ,
a
n
都是奇
数。于是
a
1
a
2
a
n
是奇数个奇数之和，
不可
能等于零，这与题设矛盾，所以2
n
，即在
a
1
,
a
2
, ,
a
n
中至少有一个偶数。如果只有一个偶数，不妨设为
a
1
，那么2
。此
|
ai
（2
i
n
）
时有等式
a
2
a
n
=
a
1
，
在上式中，左端是(
n
1)个奇数之和，右端是偶
数，这是不可能的，因此，在
a
1
,
a
2
, ,
a
n
中至
少有两个偶数，即4
n
。
例9
若
n
是奇数，则8
n
2
1。
解
设
n
= 2
k
1，则
n
2
1=
(2
k
1)
2
1 =
4
k
(
k
1)。
* *
在
k
和
k
1中有一个是偶数，所以8
n
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
=
8
A
1
1，
a
2
2
=
8
A
2
1，
a
3
2
=
8
A
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
为奇数，<
br>a
2
，
a
3
为偶数，则存在整数
A
1
，
A
2
，
A
3
，使得
a
1
2
= 8
A
1
1，
a
2
2
= 8
A
2
r
，
a
3
2
= 8
A
3
s
，
于是
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
p
mn
pq
，则
m
p
mq
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)
证明 存在性
若
b
a
，
a
=
bq
，
q
Z，
可取
r
=
0。若
b
|
a
，考虑集合
A
= {
a
kb
；
k
Z },
其中Z表示所有整数的集合，以后，仍使用此记
号，并以N表示所有正整数的集合。
在集合
A
中有无限多个正整数，设最小的
正整数是
r
=
a
k
0
b
，则必有
0 <
r
< |
b
|， (2)
|
a
，所以
r
|
b
|。于是否则就有
r
|
b
|。因为
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
}
中的最小正数，则对于任何
y
A
，
y
0
y
；特别
地，
y0
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
= 3
q
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
要取相同的值，<
br>不妨设
r
1
=
r
2
=
r
3
=
r
（
r
= 0，1或2），此时
a
1
a
2
a
3
= 3(
q
1
q
2
q
3
)
3
r
可以被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有整数解，则
3
f
(
1) =
a
0
a
1
a
2
(
1)
n
a
n
。
解
对任何整数
x
，都有
x
= 3
q
r
，
r
= 0，1或2，
q
Z。
(ⅰ)
若
r
= 0，即
x
=
3
q
，
q
Z，则
f
(
x
) =
f
(3
q
) =
a
n
(3
q
)
n
a
1
(3
q
)
a
0
= 3
Q
1
a
0
= 3
Q
1
f
(0)，
* *
其中
Q
1
Z，由于
f
(0)不是3的倍数，所以
f
(
x
)
0；
(ⅱ) 若
r
= 1，即
x
= 3
q
1，
q
Z，则
f
(
x
) =
f
(3
q
1) =
a
n
(3
q
1)
n
a
1
(3
q
1)
a
0
= 3
Q
2
a
n
a
1
a
0
=
3
Q
2
f
(1)，
其中
Q
2
Z。由于
f
(1
)不是3的倍数，所以
f
(
x
)
0。
因此若
f
(
x
) =
0有整数解
x
，则必是
x
= 3
q
2 =
3
q
1，
q
Z，于是
0
=
f
(
x
) =
f
(3
q
1) =
a
n
(3
q
1)
n
a
1
(3
q
1)
a
0
= 3
Q
3
a
0
a
1
a
2
(
1)
n
a
n
=
3
Q
3
f
(
1)，
* *
其中
Q
3
Z。所以3
f
(
1) =
a
0
a
1
a
2
(
1)
n
a
n
。
例5
证明：对于任意的整数
n
，
f
(
n
) =
3
n
5
5
n
3
7
n
被15整除。
解 对于任意的正整数
n
，记
n
= 15
q
r
，0
r
< 15。
由例1，
n
2
= 15
Q
1
r
1
，
n
4
=
15
Q
2
r
2
，
其中
r
1
与
r
2
分别是
r
2
与
r
4
被15除的余数。
以
R
表示3
n
4
5
n
2
7被15除的余数，
则
R
就是3
r
2
5
r
1
7被15除的余数，而且
f
(
n)
被15除的余数就是
rR
被15除的余数，记为
R
。
当
r
= 0时，显然
R
=
0，即153
n
5
5
n
3
7
n
。
* *
对于
r
= 1, 2,
3, , 14的情形，通过计算
列出下表：
r
=
1, 14 2, 13
5, 10 6, 9 7, 8
r
1
= 1 4
10 6 4
r
2
= 1 1
10 6 1
R
=
0 0
12 10 0
R
= 0
0
0 0 0
这证明了结论。
3, 12
4, 11
9 1
6 1
10 0
0 0
* *
例6
设
n
是奇数，则16
n
4
4
n
2
11。
解 我们有
n
4
4
n
2
11 =
(
n
2
1)(
n
2
5)
16。
由第一节例题9，有8
n
2
1，由此及2
n
2
5
得到16(
n
2
1)(
n
2
5)。
例7
证明：若
a
被9除的余数是3，4，5
或6，则方程
x
3
y
3
=
a
没有整数解。
解
对任意的整数
x
，
y
，记
x
=
3
q
1
r
1
，
y
=
3
q
2
r
2
，0
r
1
,
r
2
< 3。
则存在
Q
1
,
R
1
,
Q
2
,
R
2
Z，使得
x
3
= 9
Q
1
R
1
，
y
3
= 9
Q
2
R
2
，
其中
R
1
和
R<
br>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. 证明：12
n
4
2
n
3
11
n
2
10
n
，
n
Z。
2. 设3
a
2
b
2
，证明：3
a
且3
b
。
3. 设
n
，
k
是正整数，证明：
n
k
与
n
k
+ 4
的个位数字相同。
4.
证明：对于任何整数
n
，
m
，等式
n
2
(
n
1)
2
=
m
2
2不可能成立。
5.
设
a
是自然数，问
a
4
3
a
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
)。
由于每个非零整数的约数的个数是有限的，
所以最大公约数是存在的，并且是正整数。
如果(
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
或
p
a
；
(ⅴ) 若
a
=
bq
r
，则(
a
,
b
)
=
(
b
,
r
)。
证明 (ⅰ)(ⅳ)留作习题。
(ⅴ) 由第一节定理1
可知，如果
d
a
，
d
b
，
则
有
d
r
=
a
bq
，反之，若
d
b
，
d
r
，则
d
a
=
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
中最小的正数，则<
br>y
0
=
(
a
1
,
a
2
,
,
a
k
)。
证明
设
d
是
a
1
,
a
2
, ,
a
k
的一个公约数，
则
d
y
0
，所以<
br>d
y
0
。另一方面，由第二节例2
知，
y0
也是
a
1
,
a
2
, ,
a<
br>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
)。
这个推论对最大公约数
的性质做了更深的
刻划：最大公约数不但是公约数中的最大的，而
且是所有公约数的倍数。
推论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，那么由
d
a
（推出
d
a1
x
1
a
2
x
2
i
1
i
k
）
a
k
x
k
=
1，这是不可能的。所以有(
a
1
,
a
2
,
,
a
k
)
= 1。证毕。
定理4
对于任意的整数
a
，
b
，
c
，下面的
结论成立：
(ⅰ) 由
b
ac
及(
a
,
b
)
=
1可以推出
b
c
；
(ⅱ) 由
b
c
，
a
c
及(
a
,
b
)
=
1可以推出
ab
c
。
证明 (ⅰ)
若(
a
,
b
)
=
1，由定理2，存在
整数
x
与
y
，使得
ax
by
=
1。
因此
acx
bcy
=
c
。
* *
(2)
由上式及
b
ac
得到
b
c
。结论(ⅰ)得证；
(ⅱ)
若(
a
,
b
)
=
1，则存在整数<
br>x
，
y
使得
式(2)成立。由
b
c
与
a
c
得到
ab
ac
，
a
b
bc
，
再由式(2)得到
ab
c
。
结论(ⅱ)得证。证毕。
推论1 若
p
是素数，则下述结论成立：
(ⅰ)
p
ab
p
a
或
p
b
；
(ⅱ)
p
a
2
p
a
。
证明 留作习题。
推论2 若 (
a
,
b
)
=
1，则(
a
,
bc
)
=
(
a
,
c
)。
证明 设
d
是
a
与
bc
的一个公约数，则
d
a
，
d
bc
，
由式（2）得到，
d
|
c
, 即
d
是
a
与
c
的公约数。另一方面，若
d
是
a
与
c
的
公
约数，则它也是
a
与
bc
的公约数。因此，
a
与
c
的公约数的集合，就是
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<
br>
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
的定义，依次
得出
d
a
1
，
d
a
2
d
d
2
，
d
d
2
，
d
a
3
d
d
3
，
* *
d
d
n
1
，
d
a
n
d
d
n
，
因此
d
n
是
a
1
,
a
2
, ,
a
n
的公约数中的最大者，
即
d
n
=
(
a
1
,
a
2
, ,
a
n
)。证毕。
例1
证明：若
n
是正整数，则
既约分数。
解 由定理1得到
(21
n
4, 14
n
3)
=
(7
n
1,
14
n
3)
=
(7
n
1, 1)
=
1。
注：一般地，若(
x
,
y
) =
1，那么，对于任
意的整数
a
，
b
，有
(
x
,
y
) = (
x
ay
,
y
) = (
x
ay
,
y
b
(
x
ay
)) =
(
x
ay
, (
ab
1)
y
bx
)，
因此，
xay
是既约分数。
(ab1)ybx
21n4
是
14n3
*
*
例2 证明：121
|
n
2
2
n
12，
n
Z。
解
由于121
=
11
2
，
n
2
2
n
12
=
(
n
1)
2
11，所以，若
11
2
(
n
1)
2
11，
(3)
则11(
n
1)
2
，因此，由定理4的推论1得到
11
n
1，11
2
(
n
1)
2
。
再由式(3)得到
11
2
11，
这是不可能的。所以式(3)不能成立。
注：这个例题的一般形式是：
设
p
是素数，
a
，
b
是整数，则
|
(
an
b
)
k
p
k
1
c
，
p
k<
br>
其中
c
是不被
p
整除的任意整数，
k
是任
意的大
于1的整数。
* *
例3
设
a
，
b
是整数，且
9
a
2
ab
b
2
，
(4)
则3(
a
,
b
)。
解
由式(4)得到
9(
a
b
)
2
3
ab
3(
a
b
)
2
3
ab
3(
a
b
)
2
3
a
b
(5)
9(
a
b
)
2
。
再由式(4)得到
93
ab
3
ab
。
因此，由定理4的推论1，得到
3
a
或3
b
。 若3
a
，由式(5)得到3
b
；若3
b
，由(5
)
式也得到3
a
。因此，总有3
a
且3
b
。
由定理2的推论推出3(
a
,
b
)。
* *
例4
设
a
和
b
是正整数，
b
> 2，则2
b
1
|
2
a
1。
解 (ⅰ) 若
a
<
b
，且
2
b
12
a
1。
(6)
成立，则
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
=
2
r
((2
b
1)
Q
1)
1 =
(2
b
1)
Q
(2
r
1)，
其中
Q
是整数。因此
2
b
12
a
1 2
b
12
r
1，
在(ⅰ)中已经证明这是不可能的，所以式(6)不能
成立。
|
2
a
1。
综上证得2
b
1
* *
习 题
三
1. 证明定理1中的结论(ⅰ)—(ⅳ)。
2. 证明定理2的推论1,
推论2和推论3。
3. 证明定理4的推论1和推论3。
4.
设
x
，
y
Z，172
x
3
y
，证明：179
x
5
y
。
5. 设
a
，
b
，
c
N，
c
无平方因子，
a
2
b
2
c
，
证明：
a
b
。
32n1
6.
设
n
是正整数，求
C
1
2n
,C
2n
,<
br>
,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
的最小公倍
数，记为[
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
|]；
(ⅳ)
若
a
b
，则[
a
,
b
] =
|
b
|。
证明 留作习题。
由定理1中的结论(ⅲ)可知，在讨论
a
1
,
a
2
,
,
a
k
的最小公倍数时，不妨假定它
们都是正整
数。在本节中总是维持这一假定。
最小公倍数和最大公约数之间有一个很重
要的关系，即下面的定理。
定理2
对任意的正整数
a
，
b
，有
* *
[
a
,
b
] =
ab
。
(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
所以由第三节定理4得
,
)
= 1，
(a,b)(a,
b)
b
|
k
1
，即k
1
b
t<
br>，
(a,b)(a,b)
其中
t
是某个整数。将上式代入式(1)得到
m
=
ab
t
。
(2)
(a,b)
* *
另一方面，对于任意的整数
t<
br>，由式(2)所确
定的
m
显然是
a
与
b
的公
倍数，因此
a
与
b
的
公倍数必是式(2)中的形式，其中
t
是整数。当
t
= 1时，得到最小公倍数
[
a
,
b
] =
证毕。
推论1
两个整数的任何公倍数可以被它
们的最小公倍数整除。
证明 由式(2)可得证。证毕。
这个推论说明：两个整数的最小公倍数不但
是最小的正倍数，而且是另外的公倍数的约数。
推论2
设
m
，
a
，
b
是正整数，则[
ma
,
mb
]
=
m
[
a
,
b
]。
证明 由定理2及第三节定理2的推论得
ab
。
(a,b)
* *
到
m
2
abm
2
abmab
[
ma
,
mb
]
=
=
m
[
a
,
(ma,mb)m(a,b)(a,b)
b
]。
证毕。
定理3
对于任意的
n
个整数
a
1
,
a
2
,
,
a
n
，
记
[
a
1
,
a
2
] =
m
2
，[
m
2
,
a
3
] =
m
3
，，[
m
n
2
,
a
n
1
]
=
m
n
1
，[
m
n
1
,
a
n
] =
m
n
，
则
[
a
1
,
a
2
, ,
a
n
] =
m
n
。
证明 我们有
m
n
= [
m
n
1
,
a
n
]
m
n
1
m
n<
br>，
a
n
m
n
，
m
n
1
= [
m
n
2
,
a
n
1
]
m
n
2
m
n
1
m
n
，
* *
a
n
m
n
，
a
n
1
m
n
1
m
n
，
m
n
2
= [
m
n
3
,
a
n
2
]
m
n
3
m
n
2
m
n
，
a
n
m
n
，
a
n
1
m
n
，
a
n
2
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
。
证明 留作习题。
定理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
得到
[
a
1
,
a
2
]
=
a
1
a
2
=
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
a
1
a
2
= [
a
1
,
a
2
] =
a
1
a
2
(
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
k1
(m
k
,a
k1
)
* *
=
a
1
a
2
a
k
a
k
+ 1
，
即
m
k
=
a
1
a
2
a
k
，
(m
k
,a
k1
)
显然
m
k
a
1
a
2
a
k
，(
mk
,
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<
br>1
m
2
m
k
整除某个整数
Q
，只
需证明对于每
个
i
，1
i
k
，都有<
br>m
i
Q
。这一点在实际计算
中是很有用的。对于函数
f
(
x
)，要验证命题
“
m
f
(n
)，
n
Z”是否成立，可以用第二节例5
中的方法，验证“
m
f
(
r
)，
r
= 0, 1, ,
m
1”
是否成立。这需要做
m
次除法。但是，若分别
验证“
m
i
f
(
r
i
)，
r<
br>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
，
([a,b],c)
(9)
由第三节定理5和定理2的推论，
(
ab
,
bc
,
ca
) = (
ab
, (
bc
,
ca
)) = (
ab
,
c
(
a
,
b
))
=
(
ab,
abc
)
(ab[a,b],abc)
ab([a,b],c)
。
[
a,b][a,b][a,b]
(10)
联合式(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
]]
解 因为[
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
]。
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)
其中
=
15
。
2
证明
容易验证
2
=
1。
当
n
= 3时，由
F
3
= 2
>
可知式(2)成立。
15
=
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
,
b
N，
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
2
r
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)得
* *
b
n
=
(
即
15
n
)
，
2
log
10
b
n
log
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，
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 设<
br>a
和
b
是正整数，那么只使用被2
除的除法运算和减法运算就可以计算
出(
a
,
b
)。
解 下面的四个基本事实给出了证明：
(ⅰ) 若
a
b
，则(
a
,
b
) =
a
；
2
|
a
1<
br>，b2
b
1
，2
|
b
1，(ⅱ) 若
a
=
2
a
1
，
1，则
(
a
,
b
) = 2
(2
a
1
,
b
1
)；
|
a，b2
b
1
，2
|
b
1
，则(
a
,
b
)
= (ⅲ) 若
2
(
a
,
b
1
)；
(ⅳ) 若
2
|
a，2
|
b，则(
a,b)
(|
ab
|
,b
)
。
2
在
实际计算过程中，若再灵活运用最大公约
数的性质（例如第三节定理4的推论），则可使
得求最
大公约数的过程更为简单。
例2 用辗转相除法求(125,
17)，以及
x
，
* *
y
，使得
125
x
17
y
= (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。因此
经过若干次放硬币后，
必可使所有盒子中的硬币数目相同。
* *
习 题 五
1. 说明例1证明中所用到的四个事实的
依据。
2.
用辗转相除法求整数
x
，
y
，使得1387
x
162
y
= (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<
br> 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)<
br>的唯一性。
假设
p
i
（1
i
k
）与
q
j
（1
j
l
）都是
素数，
* *
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
必有形式 <
br>
k
1
2
p
2
p<
br>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
，
M
N，
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
）都是非负整数，则
k
1
p
k
(
a
,
b
) =
p
1
，
i
=
min{
i
,
i
}，1
i
* *
k
，
k
1
[
a
,
b
] =p
1
1
p
k
q
1
q
l
l
r
1
1
rs
s
，
i
=
max{
i
,
i
}，1
i
k
。
证明 留作习题。
为了方便，推论2常叙述为下面的形式：
推论2
设正整数
a
与
b
的标准分解式是
k
1
2
1
1
k
ap
1p
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<
br>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
53429
=
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
，
2
3
51287 =
2
3
53
2
143 =
其中
p
1
,
p
2
, ,
p
k
是互不相同的素数，
i
，
i
（1
i
k
）都是非负整数。由定理1推论2
，有
* *
k
1
1
(a,b)p
1
p
2
p
k
，<
br>
i
min{
i
,
i
}，1
ik，
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<
br>}
p
i
min{
i
,
i
}max{
p
i
i
i
i1
k
=
ab
；
(ⅱ) 设
a
p
i
i
，b
p
i
i
，c
p
i
i
，
i1i1i1
kkk
其中
p
1
,
p
2
, ,
p
k
是互不相同的素数，
i
，
i
，
（都是非负整数。由定理1推论2
，
i
1
i
k
）
有
(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
这样的问题。
例3
证明：
N1
2）不是整数。
解 设
3
k
2
n
1 < 3
k
+ 1
。
对于任意的1
i
n
，2
i
1
3
k
，记
2
i
1
=
3
i
Q
i
，
Q
i
Z，
111
（
n
352n1
* *
由第一节例5，知
i
k
1。因为3
k
1
Q
1
Q
2
Q
2
n
1
是整数，所以，如果
N
是整数，
则存在整数
Q
，使得
3
k
1
Q
1
Q
2
Q
2
n
1
N
=
Q
3
k
1
Q
1
Q
2
Q
2
n
1
1
3
k
。
由于3
所以上式右端不
是整数，
|
Q
1
Q
2
Q
2
n<
br>1
，
这个矛盾说明
N
不能是整数。
习 题 六
1. 证明定理1的推论1。
2. 证明定理1的推论2。
3.
写出22345680的标准分解式。
4. 证明：在1, 2, ,
2
n
中任取
n
1数，
其中至少有一个能被另一个整除。
* *
5. 证明：
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
。
第七节
函数[
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
] =
[x][y]
[x][y]1
若{x}{y}1
若{x}{y}1
[x]
(ⅴ) [
x
]
=
[x]1
0
(ⅵ)
{
x
} =
1{x}
若xZ
若xZ<
br>若xZ
若xZ
；
。
证明 留作习题。
定理2
设
a
与
b
是正整数，则在1, 2, ,
a
中能被
b
整除的整数有
[
a
]
个。
b
证明 能被
b
整除的正整数是
b
,
2
b
, 3
b
, ，
因此，若数1, 2, ,
a
中能被
b
整除的整数有
k
个，则
kb
a
< (
k
1)
b
k
证毕。
a
a
<
k
1
k
=
[]
。
b
b
* * 由定理2我们看到，若
b
是正整数，那么
对于任意的整数
a
，有
ab
[
a
]
b
{
a
}
，
bb
即在带余数除法
a
=
bq
r
，0
r
<
b
中有
q[
a
]
，rb
{
a
}
。
bb
1
2
k
p
2
p
定理3 设
n
是正整数，
n
!
=
p
1
k
是
n
!的标准分解式，则
i
=
[
r1
n
pi
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
!) =
1
n
1
2
n
2
3
n
3
，
(2)
显然，
n
j
就是在1, 2, ,
n
中满足
p
j
a
并
且
p
j
+
1
|
a
的整数
a
的个数，所以，由定理2
有
n
j
=
[
n
p
]
[
j
n
p
j1
]
。
将上式代入式(2)，得到
p(n!)1
([
n
]
[
n
2])
2
([
n
2
]
[
n
3
])
3
([
n
3
]
[
n<
br>4
])
p
ppppp
n
p
r
[
r1
]
。
即式(1)成立。证毕。
推论 设
n
是正整数，则
n
!
=
p
r1
pn
[
p
r
]
n
，
* *
其中
表示对不超过
n
的所有素数
p
求积。
pn
定理４ 设
n
是正整数，1
k
n
1，则
C
k
n
n!
N。
k!(nk)!
(3)
若
n
是素数，则
n
C
k
n
，1
k
n
1。
证明 由定理3，对于任意的素数<
br>p
，整数
n
!，
k
!与(
n
k
)!的标准分解式中所含的
p
的指
数分别是
[
r1
n
p
]
，
[
rr1
k
p
nk
]
与
[]
。
rr
r1
p
利用定理1可知
[
r1
n
p
]
[
r
r1
k
p
nk
]
[]
，
rr
r1
p
因此
C
k
n
是整数。
若
n
是素数，则对于1
k
n
1，有
* *
(
n
,
k
!) = 1，(
n
, (
n
k
)!) = 1 (
n
,
k
!(
n
k
)!) =
1，
由此及
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<
br>]
[
199
]
[]
=
47，
23
5
55
所以，所求的最大整数是
k
=
47。
例2 设
x
与
y
是实数，则
[2
x
] [2
y
] [
x
]
[
x
y
] [
y
]。
(4)
解 设
x
= [
x
]
，0
< 1，
y
=
[
y
]
，
* *
0
< 1，则
[
x
] [
x
y
] [
y
] = 2[
x
]
2[
y
] [
]，
(5)
[2
x
] [2
y
] =
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]n
n12n12n(n1)
2n12n14n2，
所以
[nn1][4n2]
。
若上式中的等号不成立，即
[nn1][4n2]
，
(8)
则存在整数
a
，使得
[nn1]a[4n2]
，
因此
2n12n(n1)a
2
4n2，
22
2nna2n12n1，
(2
n
1)
2
1< (
a
2
2
n
1)
2
(2
n
1)
2
，
所以
* *
a
2
2
n
1
= 2
n
1
a
2
= 4
n
2。
(9)
但是，无论2
a
或2
<
br>|
a
，式(9)都不能成立，这
个矛盾说明式(8)不能成立，即式(7)成立
。
例4 设
x
是正数，
n
是正整数，则
[x][
x
1
]
[
x
2
]
[
x
n1
]
= [
nx
]。
nnn
ii1
解 设
x
= [
x
]
，
，0
i
n
nn
1，则
[x]
[
x
1
]
[
x
2
]
[
x
n
1
]
nnn
=
n
[
x
]
i
=
n
[
x
] [
n
] =
[
n
([
x
]
)] =
[
nx
]。
例5
求[
(32)
1992
]的个位数。
解
由
(3
2)
2
5
26
得
(32)
1992
(32)
1992
=
(526)
996
(526)
996
* *
=
2
2(5
996<
br>C
996
5
994
2
2
62
9
96
6
498
)
= 10
A
2
997
6
498
= 10
A
224
498
= 10
A
2(25
1)
498
=
（10）
其中
A
和
B
都是整数。由于0 < 5
26
< 1，
所以，由式(10)可知[
(32)
19
96
]的个位数是
1。
注：一般地，如果
A
，
B
N，
A
2
>
B
，
AB
< 1，则由
k2
(A
B)
k
(A
B)
k
2(A
k
C
2
B
)
k
A
10
B
2，
可以求出[
(AB)
k
]。
例6 设
x
和<
br>y
是正无理数，
11
1
，
xy
<
br>* *
证明：数列
[
x
], [2
x
], ,
[
kx
], 与 [
y
], [2
y
], ,
[
my
],
(11)
联合构成了整个正整数集合，而且，两个数列中
的数互不相同。
解
显然
x
> 1，
y
> 1，并且
x
y<
br>。因此，
在数列(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<
br>]或者[
ky
]。
假设不然，则存在
p
,
q
N，使得
[
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
值。
3. 设
n
是正整数，
x
是实数，证明：
n2
r1
[
2
r
]
=
n
。
r1
4. 设
n
是正整数，求方程
x
2
[
x
2
] = (
x
[
x
])
2
在[1,
n
]中的解的个数。
5. 证明：方程
f
(
x
) = [
x
]
[2
x
] [2
2
x
]
[2
3
x
] [2
4
x
]
[2
5
x
] =
12345
没有实数解。
6.
证明：在
n
!的标准分解式中，2的指数
h
=
n
k
，其中
k
是
n
的二进制表示的位数码
之和。
* *
第八节 素 数
在第六节中我们已经证明了：每个正整
数可
以表示成素数幂的乘积。这就引出了一个问题：
素数是否有无穷多个？如果有无穷多个，那
么，
作为无穷大量，素数个数具有怎样的性状？这是
数论研究中的一个中心课题。本节要对这一
问题
作初步的研究。
定义1 对于正实数
x
，以
(<
br>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
，
则由
p
N
=
p
1
p
2
p
k
1
推出
p
1，这是不可能的。因此在
p
1
,
p
2
, ,
p
k
之外又有一个素数
p
，这与假设是矛盾的。所以
素数不可能是有限个。
证法Ⅱ 我们证明整数
2
1，2
2
1，2
2
1，，2
2
1，
2n
是两两互素的，从而由第六节引理1可知素数有
无限多个。
事实上，若
m
和
n
是整数，
m
>
n
0，
则
* *
2
2
1(22
(2
2
(2
2
mm1
1)(2
2
1)(2
2
m1
1)
1)(2
2
m2m1m2
1)
nnmn1
1)(2
2
m
2
1)
(2
2
1)(2
2
1)
Q(2
2
1)，
n
此处
Q
是整数。因此
2
2
1Q(2
2
1)2，
mn
故
(2
2
1,2
2
1)(2,22
1)1。
mnn
证法Ⅲ
假设只有有限个素数
p
1
,
p
2
, ,
p
k
。由第六节定理1，每个正整数可以写成
1
2
k
p
2
p
n
=
p
1
k
，
i
1，1
i
k
。
由于
(
1
1
)
1
1
p
p
，
0
所以，对于任何正整数
N
，有
*
*
1
11111
1
(
1
)
1
(
1
)
(
1
1<
br>)
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
1
641
6700417却是合数。
注2：将全体素数按大小顺序排列为
5
n
p
1
= 2，
p
2
=
3，
p
3
=
5，
p
4
，，
p
n
，，
那么由第一个证明方法可以看出
p
n
+ 1
p
1
p
2
p
n
1，
n
1。
定理2 对于
n
1，
* *
(ⅰ)
(
n
)
1
log
2
n
；
2
(ⅱ)
p
n
2
2
n
。
证明 (ⅰ)
设
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
)
，即
*
*
(
n
)
1
log
2
n
。
2
(ⅱ) 以
p<
br>m
表示第
m
个素数，在结论(ⅰ)
中取
n
=
p
m
，我们得到
m
可得到结论(ⅱ)。证毕。
注：定理2对于无穷大量
(
x
)的下界估计是
相当粗糙的。下面
的定理是已经知道的（由于其
证明较繁，故本书中不予证明）。
定理3(素数定理)
我们有
1
log
2
p
m
，由此即
2
<
br>(
x
)
x
，（
x
），
logx<
br>此处log
x
是以
e
为底的
x
的对数。
推论 以
p
n
表示第
n
个素数，则
p
n
n
log
n
（
n
）。
证明
由定理3，当
n
时，有
n
p
n
。
(2)
logp
n
* *
因此
n
log
p
n
p
n
，
log
n
loglog
p
n
log
p
n
，
log
n
log
p
n
。
由上式与式(2)得
p
n
n
log
n
（
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
是素数，则称2
n
1是Mersenne
数。
例2 形如4
n
3的素数有无限多个。
解 若不然，假设只有
k
个形如4
n
3的
素数
p
1
,
p
2
, ,
p
k
。记
N
=
4
p
1
p
p
k
– 1。
由第六节引
理1，正整数
N
可以写成若干
个素数之积。我们指出，这些素因数中至少有一
个是4
n
3形式。否则，若它们都是4
n
1的
形式，则
N
也是4
n
1的形式，这与
N
的定义
矛盾。以
p
表示这个素因数，则
p
p
i
，1
i
k
。否则若有某个
i
，1
i
k
，使得
p
=
p
i
，则
由
p
N
推出
p
1，这是不可能的。因此在
p
1,
p
2
,
,
p
k
之外又存在一个形如4
n
3的素数
p
，这
与原假设矛盾，所以形如4
n
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)
是合数。
* *
习 题 八
1.
证明：若2
n
1是素数，则
n
是2的
乘幂。
2.
证明：若2
n
1是素数，则
n
是素数。
3.
证明：形如6
n
5的素数有无限多个。
4. 设
d
是正
整数，6
|
d
，证明：在以
d
为公差的等差数列中，连续
三项都是素数的情况
最多发生一次。
5. 证明：对于任意给定的正整数
n
，必存
在连续的
n
个自然数，使得它们都是合数。
6.
证明：级数
理1注2中的记号。
n1
1
发散，此处使用了定
p
n