爆笑谷-高中毕业典礼

第十七章 整数问题
一、常用定义定理
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
≠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< br>k-1
+u
k
,0k
k-1
； < br>u
k-1
=q
k-1
u
k+1
,0k+ 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)是质数（或
aa
a
称素数），且在不计次序的意义下，表示是唯一的。
6．同余：设m≠0,若m|(a-b) ，即a-b=km，则称a与b模同m同余，记为a≡b(modm)，也称
b是a对模m的剩余。 < br>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．Fermat小定理：若p为素数，p>a,(a,p)=1，则a≡1( modp)，且对任意整数a,有a≡a(modp).
9．若(a,m)=1，则
a

(m)
≡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< br>k
是k个两两互质的正整数，则同余组：
x≡b
1
(modm
1
),x≡b
2
(modm
2
),…,x≡b
k
(modm
k
)有唯一解，
x≡
M
1
M
1
b
1
+
M
2
M
2
b
2
+…+< br>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。



2．不等分析法。
333222
例2 试求所有的正整数n，使方程x+y+z=nxyz有正整数解。
- 1 -

3．无穷递降法。
22222
例3 确定并证明方程a+b+c=ab的所有整数解。





4．特殊模法。
例4 证明：存在无穷多个正整数，它们不能表示成少于10个奇数的平方和。




5．最小数原理。
442
例5 证明：方程x+y=z没有正整数解。








6．整除的应用。
n
3

1
例6 求出所有的有序正整数数对(m,n)，使得是整数。
mn

1









7．进位制的作用
5
例7 能否选择1983个不同的正整数都不大于10，且其中没有3个正整数是等差数列中的连
- 2 -

续项？证明你的结论。







三、习题精选
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，都有
F
n
(
F< br>n
(
F
n
(
F
n
(
F
n< br>(
F
n
(
a
)

)
=1，
6
5
4321
并证明你的结论。
n+1
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不是素数。
- 3 -