唱-心海扬帆

高中数学竞赛整数问题

一、常用定义定理
1．整除：设a,b∈ Z,a≠0，如果存在q∈Z使得b=aq，那么称b可被a整除，记作a|b，且
称b是a的倍数,a 是b的约数。b不能被a整除，记作a b.
2.带余数除法：设a,b是两个给定的整数，a≠ 0，那么，一定存在唯一一对整数q与r，满
足b=aq+r,0≤r<|a|，当r=0时a|b。
3．辗转相除法：设u
0
,u
1
是给定的两个整数，u
1< br>≠0，u
1
u
0
,由2可得下面k+1个等式：
u
0
=q
0
u
1
+u
2
,02
<|u
1
|；
u
1
=q
1
u
2
+u
3
,03
2
；
u
2=q
2
u
3
+u
4
,04
3
；
…
u
k-2
=q
k-2
u
1
+u
k-1
+u
k
,0k
k- 1
；
u
k-1
=q
k-1
u
k+1
,0 k+1
k
；
u
k
=q
k
u
k+1
.
4．由3可得： （1）u
k+1
=(u
0
,u
1
)；（2）d|u
0
且d|u
1
的充要条件是d|u
k+1
；（3）存在整数x 0
,x
1
，使u
k+1
=x
0
u
0< br>+x
1
u
1
.
5．算术基本定理：若n>1且n为整数，则
np
1
1
p
2
2
p
k
k，其中p
j
(j=1,2,…,k)是质数
（或称素数），且在不计次序的意义下 ，表示是唯一的。
6．同余：设m≠0,若m|(a-b)，即a-b=km，则称a与b模同m同余 ，记为a≡b(modm)，也
称b是a对模m的剩余。
7．完全剩余系：一组数y
1
,y
2
,…,y
s
满足：对任意整数a有且仅有一个y
j
是a对模m的剩余，
即a≡y
j
(modm)，则y
1
,y
2
,…,y
s
称为模m的完全剩余系。
p-1p
8．Fe rmat小定理：若p为素数，p>a,(a,p)=1，则a≡1(modp)，且对任意整数a,有a≡a(modp).
9．若(a,m)=1，则
a

(m)
aa
a
≡1(modm),

(m)称欧拉函数。
a
1
1
a
2
2
a
k
k
10．（欧拉函数值的计算公式 ）若
mppp
，则

(m)=
m

(1i1
k
1
).

p
i
11．（孙子定理）设 m
1
,m
2
,…,m
k
是k个两两互质的正整数，则同余组 ：
x≡b
1
(modm
1
),x≡b
2
(mod m
2
),…,x≡b
k
(modm
k
)有唯一解，
x≡
M
1
M
1
b
1
+
M
2M
2
b
2
+…+
M
k
M
k
b
k
(modM)，
其中M=m
1
m
2
m
k
；
M
i
=
''
'
M
'
，i=1 ,2,…,k；
M
i
M
i
≡1(modm
i
),i =1,2,…,k.
m
i
二、方法与例题
1．奇偶分析法。
例1 有n个整数，它们的和为0，乘积为n，（n>1），求证：4|n。
[证明] 设这n个整数为a
1
,a
2
,…,a
n
，则a
1< br>,a
2
,…,a
n
=n， ①

a
1
+a
2
+…+a
n
=0。 ②
首先n为偶数，否则a
1
,a
2
,…,a
n
均 为奇数，奇数个奇数的和应为奇数且不为0，与②矛盾，
所以n为偶数。所以a
1
,a
2
,…,a
n
中必有偶数，如果a
1
,a
2
,…,a
n
中仅有一个偶数，则a
1
,a
2
,…,an
中还有奇数个奇数，从而a
1
+a
2
+…+a
n也为奇数与②矛盾，所以a
1
,a
2
,…,a
n
中必有 至少2个
偶数。所以4|n.
2．不等分析法。
333222
例2 试求所有的正整数n，使方程x+y+z=nxyz有正整数解。
2332333
解 设x ,y,z为其正整数解，不妨设x≤y≤z，则由题设z|(x+y)，所以z≤x+y，但x
x
3
y
3
22332222
≤xz,y≤yz，因而z=nxy-≥nxy -(x+y)，故x+y≥z≥[nxy-(x+y)]，所以
2
z
23222
nxy≤2nxy(x+y)+x+y，所以nxy<
2


x

y



nx
3

ny
3
。若x≥2，则4≤

2442233

11

11< br>nxy<
2



11

1
211
1
2
≤3，矛盾。所以x=1，所以ny<，此式当且

< br>
3
33

yn
ny
ny

xy

nx
23323
仅当y≤3时成立。又z|(x+y)，即z|(1+y) ，所以只有y=1,z=1或y=2,z=3，代入原方
程得n=1或3。
3．无穷递降法。
22222
例3 确定并证明方程a+b+c=ab的所有整数解。
解 首先( a,b,c)=(0,0,0)是方程的整数解，下证该方程只有这一组整数解。假设(a
1
, b
1
,c
1
)
是方程的另一组整数解，且a
1
,b
1
,c
1
不全为0，不妨设a
1
≥0,b
1
≥0,c
1
≥0且
a
1
b
1
c
1< br>0
，
由
a
1
b
1
≡1或0(mod4)知 a
1
,b
1
,c
1
都是偶数(否则
a
1< br>b
1
c
1
22222
222
a
1
2
b
1
2
(mod4))，从而
(
a
1
b
1
c
1
abc
,,)
是 方程x
2
+y
2
+z
2
=2x
2
y
2
的一组整数解，且 不全为0，同理可知
1
,
1
,
1
也都
222222
a
1
b
1
c
1
,
2
,
2
)
为方程x
2
+y
2
+z
2
=2
4
x
2
y
2
的解。这一过程可以无限进行下去，另一方面
2
222
kkk
是偶数
(
a
1
,b
1
,c
1
为有限的整数，必存在k∈N,使2>a
1
,2>b
1,2>c
1
，从而
a
1
b
1
c
1,
k
,
k
不是整数，矛盾。
k
222
所以该方 程仅有一组整数解(0,0,0).
4．特殊模法。
例4 证明：存在无穷多个正整数，它们不能表示成少于10个奇数的平方和。
222
[证明] 考虑形如n=72k+66,k∈N的正整数，若
nx
1
x
2
 x
s
，其中x
i
为奇数，
i=1,2,…,s且1≤s≤9。因 为n≡2(mod8)，又
x
i
≡1(mod8)，所以只有s=2.所以
n x
1
x
2
，
又因为
x
i
≡2或0(m od3)，且3|n，所以3|x
1
且3|x
2
，所以9|n。但n=72k +66≡3(mod9)，
2
2
22

矛盾。所以n不能表示成 少于10个奇数的平方和，且这样的n有无穷多个。
5．最小数原理。
442
例5 证明：方程x+y=z没有正整数解。
[证明] 假设原方程有一组正整数解(x
0
,y
0
,z
0
)，并且z
0
是所有正整数解z中最小的。 因此，
2222
22222
22
(x
0
)(y
0
)z
0
，则
x
0

a-b,
y
0
=2ab,z
0
=a+b，其中(a,b)=1,a,b一奇一偶。假设a
2222
为偶数，b为奇数，那么
x
0
z
0
0
(mod4)，而
x
0
ab3
(mod4)，矛盾，所以a
2 22
为奇数，b为偶数。于是，由
x
0
ba
得x0=p-q,b =2pq,a=p+q（这里(p,q)=1,p>q>0,p,q
2222
222
为 一奇一偶）。从而推得
y
0
2ab4pq(pq)
，因为p,q,p+ q两两互质，因此它们必
22
须都是某整数的平方，即p=r,q=s,p+q=t，从而r4 +s4=t2，即(r,s,t)也是原方程的解，
22222
且有t6．整除的应用。
22222
n
3
1
例6 求出所有的有序正整数数对(m,n)，使得是整数。
mn1
解 （1）若n=1,则2
是整数，所以m-1=1或2，所以(m,n)=(2,1),(3,1).
m1< br>n
3
1n
3
122
n
2
n1 
（2）若m=1,则，所以n-1=1或2，所以
n1n1n1
(m,n)= (1,2),(1,3).
(m
3
n
3
1)m
3< br>(n
3
1)m
3
1
m
3
n
3< br>1

（3）若m>1，n>1，因为是整数，所以也是
mn1mn1mn1
整数，所以m,n是对称的，不妨设m≥n，
n
3
1n3
nn11
n
ⅰ）若m=n，则
2
为整数，所以n =2,m=2.
n1
n1n
2
1
n
3
1
ⅱ）若m>n，因为n+1≡1(modn),mn-1≡-1(modn)，所以≡-1(modn) .
mn1
3
n
3
1n
3
1n
3< br>11
n,
所以存在k∈N，使kn-1=,又kn-1=
mn1n 1
mn
2
1n
2
1
n
3
1n2
12
1
n1.
所以(k-1)n<1+,所以k=1，所以 n=1=,所以
m
mn1n1n1
n1
所以n-1=1或2，所以 (m,n)=(5,3)或(5,2).
同理当m综上(m,n)=(1,2),(2,1),(1,3),(3,1),(2,2),(2,5),(5 ,2),(3,5),(5,3).
7．进位制的作用

例7 能否选择1 983个不同的正整数都不大于10，且其中没有3个正整数是等差数列中的
连续项？证明你的结论。
5
解 将前10个自然数都表示为三进制，在这些三进制数中只选取含数字0或1（而不含数
字2）的数组成数集T，下证T中的数符合要求。
105115
（1）因为3<10 <3,所以前10个自然数的三进制至多由11个数字组成，因而T中的元素
21011
个数共 有1+2+2+…+2=2-1=2047>1983（个）。这是因为T中的k位数的个数相当于用0，
k-1
1这两个数在k-1个位置上可重复的全排列数（首位必须是1），即2,k=1,2,…,1 1.
2105
（2）T中最大的整数是1+3+3+…+3=88573<10。
（3）T中任意三个数不组成等差排列的三个连续项。否则，设x,y,z∈T,x+z=2y，则2y必
只含0和2，从而x和z必定位位相同，进而x=y=z，这显然是矛盾的。
三、习题精选
2
1．试求所有正整数对(a,b)，使得(ab-a+b+1)|(ab+1).
2222
2．设a,b,c∈N
+
，且a+b-abc是不超过c+1的一个正整数， 求证：a+b-abc是一个完全平
方数。
22
3．确定所有的正整数数对(x,y )，使得x≤y，且x+1是y的倍数，y+1是x的倍数。
n2
4．求所有的正整数n，使得存在正整数m,(2-1)|(m+9).
5．求 证：存在一个具有如下性质的正整数的集合A，对于任何由无限多个素数组成的集合，
存在k≥2及正整 数m∈A和n

A，使得m和n均为S中k个不同元素的乘积。
6．求最小的正整数 n(≥4)，满足从任意n个不同的整数中能选出四个不同的数a,b,c,d使
20|(a+b-c- d).
7.对于正整数a,n,定义F
n
(a)=q+r，其中q,r为非负整数， a=qn+r且0≤r≤n，求最大正整
数A，使得存在正整数n
1
,n
2< br>,…,n
6
，对任意正整数a≤A，都有
5
F
n
(< br>F
n
(
F
n
(
F
n
(
F< br>n
(
F
n
(
a
)

)
=1 ，并证明你的结论。
6
5
4321
8．设x是一个n位数，问：是否总存在 非负整数y≤9和z使得10z+10x+y是一个完全平
方数？证明你的结论。
9．设a, b,c,d∈N
+
,且a>b>c>d,ac+bd=(b+d+a-c)(b+d-a+c) 。证明：ab+cd不是素数。


n+1