高中数学竞赛专题讲座---竞赛中的数论问题

竞赛中的数论问题的思考方法

一. 条件的增设
对于一道数论命题 ，我们往往要首先排除字母取零值或字母取相等值等“平凡”的情况，这样，利用
字母的对称性等条件， 往往可以就字母间的大小顺序、整除性、互素性等增置新的条件，从而便于运用各
种数论特有手段。
1. 大小顺序条件
与实数范围不同，若整数
x
，
y
有大 小顺序
x
<
y
，则必有
y
≥
x
+1，也可 以写成
y
=
x
+
t
，其中整数
t
≥1。
例1. （IMO-22）设
m
，
n
是不大于1981的自然数，< br>(n
2
?nm?m
2
)
2
?1
，试求
m?n
的最大值。
解：易知当
m
=
n
时,
m? n?2
不是最大值。于是不访设
n
>
m
,而令
n
=
m
+
u
1
，
n
>
u
1
≥ 1，得
(m
2
?
mu
1
?

22
22
(m
2
?mu
1
?u
1
2
)
2
?1
。同理，又可令
m
=
u
1
+
u
2
，
m
>
u
2
≥1。如此继续下去将得
u
k+1
=
u
k
=1，而
u
i?1
?u
i
?u
i?1
，
i
≤
k
。
故u
k?1
,u
k
,
?
,u
2
,u1
,m,n
是不大于1981的裴波那契数，故
m
=987，
n
=1597。
222
例2. （匈牙利—1965）怎样的整数
a
，
b
，
c
满足不等式
a?b?c?3?ab?3b?2c?

b
?1)
2
?(c?1)
2
?1?0
。因为所求的 都是整数，所以原不等
2
b
2
b
22
222
式可以 改写为：
a?b?c?4?ab?3b?2c
，变形为：
(a?)?3(?1)?(c ?1)?0
，从而只
22
解：若直接移项配方，得
(a?)?3(< br>2
b
2
有
a
=1，
b
=2，
c=1。
2. 整除性条件
对于整数
x
，
y
而言，我 们可以讨论其整除关系：若
x
|
y
，则可令
y
=
t x
；若
x
?
y
，则可令
y
=
tx
+
r
，0<
r
≤|
x
|-1。这里字母
t
，
r
都是整数。进一步，若
q|a
，
q|b
且
b? a
，则
b?a?q
。结合高斯函数，设
n
除以
k
， 余数为
r
，则有
n?
??
k?r
。还可以运用抽屉原理，为 同余增设一些条件。整除性与大小顺序
k
结合，就可有更多的特性。
例3. 试证两 相继自然数的平方之间不存在自然数
a
<
b
<
c
<
d
，使得
ad
=
bc
.
解：在假定了
n
2
?a?b?c?d?(n?1)
2
之后，可设
?
n
?
??
cdp
??,(p,q)?1
。（显然
p
>
q
）由
p
，
abq
p
的范围进行估
q
q
的互素性易知必有
q
|
a
，
q
|
b
。这样，由
b
>
a
即得
b?a?q
。（有了三个不等式， 就可对
1q?1pdd(n?1)
2
计），从而
1??
。于是将导致 矛盾的结果：
(n?q)
2
?0
。这里，因
????
2qqqba?q
n?q
为
a
，
b
被
q
整除，我们由
b
>
a
得到的不仅是
b
≥
a
+1，而是更强的条件
b
≥
a
+
q
。
例4. （ IMO-25）设奇数
a
，
b
，
c
，
d
满 足0<
a
<
b
<
c
<
d
，
ad< br>=
bc
，若
a?d?2
k
,
是整数，试证
a
=1。

1
b?c?2
m
，这里
k
，
m

(b?c)
解：不难证明
k
，
m
的大小关系
k
>
m
。[
(a?d)
2
?4 ad?(d?a)
2
?4bc?(d?a)?4bc?(c?b)?

22< br>km
所以
2?2
。]
d?2
k
?a,c?2
m
?b
，代入
ad
=
bc
中，有
a(2
k
?a)?b(2
m
?b)
（1），
?(c?b)
2
?(b?c)
2
。
由（1）可得
b?2?a ?2?b?a
。即
2b?2a?b?a
，
2
m
(b?2k?m
a)?(b?a)(b?a)
（2）
已知
a
，b
都是奇数，所以
a
+
b
，
a
-
b< br>都是偶数，又
(a?b)?(a?b)?2a
是奇数的2倍，故
b
+< br>a
，
b
-
a
中
mk22
mk22
?
b?a?2
m?1
e
?
b?a?2
m?1
e
必有一个不是4的倍数。由（2）必有
?
或
?
。其中，
e
，
f
为正整数，且
?
b?a?2f
?
b?a?2f
[
(a?b)?(a?b)?2
m
ef
，与（2）比较可得]由于
k
>
m
，故
ef?b?2a?b?a?

2
ef?b ?a?2
k?m
是奇数。
k?m
2a?b?a?2f
。从而
e
=1，
f?b?a?2
?
b?a?2
m?1
。考虑前一情 况，有
?
由第二式可得
k?m
b?a?2f?2(b?a?2)
?
b?a?2
k?1?m
a
，故
2
m?1
?2k?1?m
a
，所以奇数
a
=1。对于后一情况，可作类似的讨论。
显然，上述解题思路中有两个技巧：一是用放缩法证明
k
<
m
；第二个是（2）式的分解，然后运用整除
的条件。
例5. 设
r(n)
为n分别除以1，2，┅，n所得的余数之和。证明存在无穷多个正整数n，使得
r(n)?r(n?1 )
。
nn
?
n
?
?
n
?
2
解 ：把
n
除以
k
的余数记为
r
k
，则有
r< br>k
?n?
??
k
。故可得
r(n)
r的表达式
r(n)?
?
r
k
?
?
(n?

k)? n
?
?
k
?
?
k
?
?
k?1k? 1
n?1
n
n?1
?
n?1
?
?
n
??
n
?
2
2
?
n
??
n?1
?
。则
k
r
k
?
?
(n?
??
k)?n?
?
??
k
。由此易得
r(n?1)?(n?1)?
?
?
r(n)?r(n?1)?(n?1)?(?
?
?
?
???
k
kk
??
????
k?1
k?1k?1
k ?1
?
k
??
k
?
n
n?1
?
n
??
n?1
?
?
n
??
n?1
?
?
1,k|n
?
n
??
n?1
?

r (n)?r(n?1)
，因此，等价于。注意到
(n?1)?(?)k
1)?(n?1 )?
?
(
??
?
?
)k
??
?
? ???
?
?
k
??
k
?
?
0,k
?
|n
????
?
k?1
?
k
??
k?
k?1
?
k
??
k
?
n?1
??< br>n?1
?
?
1,k|n
l
，因此题中的条件等价于
n
的所有真因子之和等于
n
-1。显然，取(l为正整数)，则
n
n? 2
??
?
??
k
?
|n
???
?
0,k
?
的所有真因子之和为
n
-1，而这样的
n
有无穷多 个。
例6. 试证对于任给的
m
个整数
a
1
,a
2
,
?
,a
m
，必有
s,j(1?s?j?m)
， 使得
m
|(
a
s
?a
s?1
?
?
?a
j
)

解：令
b
i
?a
1< br>?a
2
???a
i
（
i?1,2,?,m
）。若b
1
,b
2
,
?
,b
m
中有一个数被 m整除，则结论成立。
否则，各
b
i
均不能被m整除，此时可设
b< br>i
?mq
i
?r
i
(1?r
i
?m?1)< br>。这样，
m
个余数
r
1
,r
2
,
?
,r
m
只
能从1至
m
-1这
m
-1个数中 取值，由抽屉原理知，必有
k,j(1?k?j?m)
，使得
r
k
? r
j
，于是
b
j
?b
k
?m(q
j
?q
k
)
，故
m|(b
j
?b
k
)?( a
k?1
?a
k?2
?
?
?a
j
)
取
s?k?1
即得到结论。
3. 互素性的条件

2

当（
a
，
b
）=
d
>1时，我们总是作如 下考虑：令
a?a
1
d,
件的增置往往对解题有很大作用。
b?b
1
d
，则必有
(a
1
,b
1
)?1
。这种互素条
例7. （波兰64—65）设整数
a
，
b
满足2a?a?3b?b
，试证
a?b
及
2a?2b?1
都是完全平 方数。
解：
2a?a?3b?b
变形可得：
(a?b)(2a?2b?1) ?b
2
，故只要能证一个，则另一个必是。我
们在排除了字母取零或相等的情况后，可 设
a,b?0,
22
22
a?b,(a,b)?d
。这时令
a?a
1
d,b?b
1
d
，
2
2
(a1
,b
1
)?1
，从而方程变为
2da
1
?a
1
?b
1
?3db
1
2
。显然有
d|(a
1
?b
1
)
。另一方面又
a
1
?b
1
?3db
1
2
?

2da
1
??2d (
22
2
有
(a
1
?b
1
)|db
注意到
(a
1
?b
1
,b
1
)?(a
1
,b
1
)?1
，于是有
(a
1
?b
1)|d
。
b
1
?3db
1
2
?2da
1
??2d(a
1
?b
1
2
)?db
1
2
，
1
。
这样就有
d?|a
1
?b
1
|
。至此已十分容易获得命题的结论了。这里，由
a
1
与
b
1
互素导出
a
1
—
b
1
与
b
1
互素，
是证明
(a
1
?b
1
)|d
的关键 。
二. 从特殊到一般
例8. （IMO-18）试求和为1978的正整数之积的最大值。
?a
n
?10,
解：我们可通过减少加法运算的次数来选择特例，例如考虑求正整数
a
1
,a
2
,?,a
n
,
满足
a
1
?a
2
?
?

a
1?a
2
?
?
?a
n
?10,n?10,
使a
1
a
2
?a
n
最大。显然，最特殊且最简单的正整数 是1。例如取
a
1
=1，这里由
a
1
a
2
?a
n
?a
2
?a
n
?(a
2
?1)?a
n
知乘积不是最大的值。对于某些正整数取2的情况，注意到2+2=4，
2×2=4 ；2+2+2=6=3+3，2×2×2<3×3。我们发现诸
a
i
中不能取多于两个 2。对于
a
i
=5，有2+3=5，2×3>5。
因此不如把一个5拆成2与 3的和，从而使乘积变大，对于6，7等有类似的结论。这样，我们已大致可
确定诸
a
i
只应取2或3，且2的个数不超过两个。依此估计，由1978=658×3+2+2，即可猜测最大 的积为
2
2
?3
658
。
例9. （IMO—31备选题 ）设
a
，
b
是给定的正整数，现有一机器人沿着一个有
n
级 的楼梯上下升降，每上
升一次恰好上升
a
级，每下降一次恰好下降
b
级。为使机器人经过若干次上升下降后，可以从地面升到楼
梯顶，然后再返回地面，问
n
的最小值是多少？
解：为了探讨解法和结论，不妨设
a?b
。我们分b
|
a
与
a
?
b
两种情况进行讨论。对于b
|
a
的情况结
论是显而易见的：可令
a
=
s b
, 机器人上升一次，然后再连续下降s次即达到要求，故
n
=
a
.现考虑
a
?
b
。
例如，特例
a
=5，
b
=3。这时机器人先上升一次达到第五级，为使
n
最小，机器人就不应再上升，而是尽 量
下降。下降1次至第2级。此时，再上升一次到第2+5=7级，然后再一降两次到第1级，又上升至 1+5=6
级，再下降二次至0级，从而机器人已完成了上升下降的全过程，故
n
=7 。又取特例
a
=7，
b
=4。依上述方
法可得
n
= 10。通过特例，我们可作如下猜测：若
a
?
b
，且（
a
，
b
）=1，则
n
=
a+b
-1。实际上，依照上述试
验的思路，这一猜想是可以被证明的。
数论中还有很多命题是通过选取某一特殊的数作为模来讨论和 解决的。这种数往往是根据命题的一些
因素（如项的系数、字母的指数、式的形状等），通过试用来选择 和确定的，最简单的是mod2，即奇偶分
析法。其次是模3，4，5，8等。
三. 讨论极端情况
由于整数集具有最大（小）整数原理这一特性，我们往往可以从某种条件下有最大（小） 元素出发进
行讨论。例如，可考虑：（1）数列中具有某种特点的极端项；（2）数的最小因数；（3） 数的分解式中某素

3

数的最高次幂；（4）未知数的最小正整数值 ；（5）一组正整数解和的最小值。使用这种方法的实例很多。
例10. （IMO—28）设
n
>2，
f(x)?x
2
?x?n
，这里
x
为整 数。若当
0?x?
证对任何0≤
x
≤
n
-2，
f< br>(
x
)也都是素数。
解：设命题结论不成立，我们就可取使
n
时，
f
(
x
)都是素数，试
3
f
(
x< br>)为合数的最小整数
y?min{x;0?x?n?2,f(x)为合数

}< br>f(x)为合数}
。我们通过
y
2
?y?n
的最小素因数p
的讨论，将可证明
0?y?
n
，从而产生矛盾。
3
a
2
?b
2
例11. （IMO—29）设正整数
a
，
b
使
ab
+1整除
a?b
，试证是完全平方 数。
ab?1
22
a
2
?b
2
22
解：记
k?
，则正整数
k
应使方程
a?kab?b?k?0
（1），关于未知数
a
，
b
有正整
ab?1
数解。显然ab
>0，否则由
ab
≤-1就可以从（1）导出
k
<0。设< br>a
0
，
b
0
是（1）的使
a
0
+< br> b
0
最小的一组正整数
?
?kb
0
?
a< br>0
?a
0
解，不妨设
a
0
≥
b
0< br>。固定
k
与
b
0
，由（1）有
?
2
?
?b
0
?k
?
a
0
a
0
(2)
?
是整数。若
k
，由（2）知
a
0
(3)
2
?
?0
。注意到
a
0
?
b
0
? 0
，故
a
0
?
?0
。这就表明
a
0
?
，
b
0
也是不是完全平方数，则
k?b
0
，故 由（3）知
a
0
?
?a
0
，故
a
0
?
?b
0
?a
0
?b
0
。这是矛盾的。故
k
是完全平方数。 （1）的一组正整数解。易证
a
0
四. 缩小取值范围
讨论并缩小变数或式子的取值范围，是解决数论命题常用的方法之一。对数论中有关整数的命题而言，< br>这种方法有着特殊的作用：如能将取值范围确定在一有限区间内，我们就可以用有限个整数逐一进行检验。
通过取某些数为模来排除不合要求的剩余类是缩小取值范围的一个重要方法。
例12. （I MO—30备选题）设正整数
a
，
b
，
c
，
d，
m
，
n
满足
a?b?c?d?1989
，
a ?b?c?d?m
，
其中
a
，
b
，
c
，< br>d
的最大者为
n
，试求
m
与
n
的值。 解：由条件不难看出
m
是奇数。同时可对
a
+
b
+c
+
d
的取值范围作出一个估计，而在此范围内可成为
m
的数是 不多的。事实上，由柯西不等式得
a?b?c?d?21989?90
。[
(a?2
2
2222
2
1
2
1111111
b?c? d)
2
?(?

??)(
2224444
1
21111
22
b
2
?c
2
?d
d)?(??? )(a
2
?b
2
?c
2
?d
2
)
]，因而
m
只能从1，3，5，7，9这五个数中选取.再由
(a?b?c?d)?a ?

24444
?d)
2
?a
2
?b
2< br>?c
2
?d
2
知只能有
m
=7或9。因而只要证明< br>m
2
?49
，即可确定
m
2
?81
，进而< br>n
2
?25
。这里，我
们主要是利用已知的重要不等式来确定取值范围 。
例13. （IMO—19）设
a
，
b
是正整数，
a? b
除以
a
+
b
时，商为
q
，余数为
r。试求所有的数偶
a
与
b
，
22

4

使得
q
2
?r?1997
。
a
2
?b
2
解：由
q?r?1997
，可 得估计
q
≤44。于是
?45
。但
q
取得较小值时，由q
2
?r?1997
a?b
2
就使
r
增大，进 而由
r
<
a
+
b
又使
a
+
b更大。但
a
2
?b
2
?q(a?b)?r?(q?1)(a?b )
，因而
a
+
b
增大就
a
2
?b
2
使得
q
减小。这种
q
与
a
+
b
之间的制约关系表明
q
不能太小。依此思路，我们将可由q≤43导出
?46
a?b
的矛盾，从而确定了
q
=44。据此很容易求出
a
与
b
了。
五. 构造法
构造法常用来作存在性的证明。我们熟知有欧几里德关于素数 个数无限性的证明就是一个典型的例
子。另一个重要的例子是关于“存在
n
个相继自然 数都是合数”的证明：对任意的
n
，令
N
=(
n
+1)!， 则相
继的自然数
N
+2，
N
+3，…，
N
+
n
+1 （*）,是
n
个合数。我们还可以举出许多例子，如（1）试证存在无
限多个正整数
a
，使得对每一个自然数
n
，数
n?a
都是合数。（2）试证存在无限多个正整数
n
，使6
n
-1
与6< br>n
+1同为合数。（3）试证对任何自然数
n
>3，必存在素数
p，满足
n
<
p
<
n
!。解决此类命题的关键是寻找和构造所需的数或式。例如，取
a?4k
，
k
为任意非零整数，就证明了 （1）；取
n?
2
2
1
(k!?1),k?7
，就
6
证明了（2）；取
p
为
n
!-1的最小素因数，也可证明
n
<
p
<
n
!。
我们要强调指出前面（*）中的
n
个数的构造是极有启发性的。首先，其中
N
的选择还是有迹可寻的：
由“< br>n
个相继自然数”立即可联想到取
N
+1，
N
+2，…，N
+n。但
N
+1不能判定是否为合数，因而应取消，
于是立即联想到（ *）。为了保证各数是合数，就应要求
N
同时含有因数2，3，…，
n
，n
+1。这样的构造还
为我们提供了解决另一些命题的线索。例如，为证“存在
n
个相继的自然数，其中仅有一个素数”这一结
论，可从数列（1）出发进行分析：设
p
为大于
N
+1的最小素数，可以证明：
p
-
n
+1 ，…，
p
-1，
p
；除最后
一个数
p
外，都是合数 。
例14. （IMO—30）试证对于任何正整数
n
，存在
n
个 相继的自然数，它们都不是素数的整数幂。
解：我们取
N
=(2(
n
+1))!+1，考虑
N
+
j
，1≤
j
≤
n
。若
N
+
j
=(2(
n
+1))!+
j
+1=
p
m
，则显然有(
j
+1)|(
N
+
j
)，
因而必有
j
+1=
p
r
,1≤
r
≤
m
，从而
p
r?1
|p
m
。 另一方面，由
j
+1≤
n
+1知
p
r
|(n?1) !
，故
p
r?1
|(2(n?1)!
。
于是
pr?1
|(N?j)?(2(n?1))!?j?1
。这是与
j?1?p
r
矛盾的，从而证明了命题。最后还应指出，同
一命题的构造方法可以有多种，如例13中也可 令
N?((n?1)!)
2
?1
。



5