2024年11月2日发(作者：韩依云)
数学奥赛辅导第二讲整除
数学奥赛辅导 第二讲
整除
知识、方法、技能
整除是整数的一个重要内容，这里仅介绍其中的几个方面：整数
的整除性、最大公约数、最小公倍数、方幂问题.
Ⅰ. 整数的整除性
初等数论的基本研究对象是自然数集合及整数集合. 我们知道，整
数集合中可以作加、减、乘法运算，并且这些运算满足一些规律（即
加法和乘法的结合律和交换律，加法与乘法的分配律），但一般不能
做除法，即，如b a ,是整除，0≠b ，则b
a
不一定是整数. 由此引出初等数论中第一个基本概念：整数的整除
性.
定义一：（带余除法）对于任一整数a 和任一整数b ，必有惟一
的一对整数q ，r 使得
r bq a +=，b r <≤0，并且整数q 和r 由上述条件惟一确定，则
q 称为b 除a 的不完全商，
r 称为b 除a 的余数.
若0=r ，则称b 整除a ，或a 被b 整除，或称b a 是的倍数，或
称a b 是的约数（又叫因子），记为a b |.否则，b | a .
任何a 的非1,±±a 的约数，叫做a 的真约数. 0是任何整数的倍
数，1是任何整数的约数.
任一非零的整数是其本身的约数，也是其本身的倍数. 由整除的定
义，不难得出整除的如下性质： （1）若.|,|,|c a c b b a 则
（2）若.,,2,1,,|
,|1
n i Z c
b c a b a i
n
i i i i =∈∑=其中则
（3）若c a |，则.|cb ab 反之，亦成立.
（4）若||||,|b a b a ≤则.因此，若b a a b b a ±=则又,|,|. （5）
a 、b 互质，若.|,|,|c ab c b c a 则
（6）p 为质数，若,|21n a a a p 则p 必能整除n a a a ,,,21
中的某一个. 特别地，若p 为质数，.|,|a p a p n 则
（7）如在等式
∑∑===m
k k
n i i b
a 1
1
中除开某一项外，其余各项都是c 的倍数，则这一项也是c
的倍数.
（8）n 个连续整数中有且只有一个是n 的倍数. （9）任何n 个连
续整数之积一定是n 的倍数.
本讲开始在整除的定义同时给出了约数的概念，又由上一讲的算
术基本定理，我们就可以讨论整数的约数的个数了.
定理一：设大于1的整数a 的标准分解式为n n p p p p p p a n
<<
α
α
为质数，i α均为非负整数），则a 的约数的个数为
∏=+=n
i i a d 1
)1)(α（.
所有的约数和为：
∏
=+--=n
i i i p p a i 1
11
1
)(ασ.
事实上，由算术基本定理的推论知∏=+=
n
i i
a d 1
)1()(α
，而各约数的和就是
∏=+++n
i i i
i pa p
1
)1( 展开后的各项之和，所以
∏∏
==--=+++=n
i n
i i i i p p p p a i i
1111
1
)1()(αασ 例如，25200=24·32·52·7，所以
90)11)(12)(12)(14()25200(=++++=d ，
999441
71
72)25200(2335=--?--?--?--=σ.
Ⅱ. 最大公约数和最小公倍数
定义二：设a 、b 是两个不全为0的整数.若整数c 满足：b c a c
|,|，则称b a c ,为的公约数，b a 与的所有公约数中的最大者称为b a
与的最大公约数，记为),(b a .如果),(b a =1，则称b a 与互质或互素.
定义三：如果a d 是、b 的倍数，则称a d 是、b 的公倍数. b a
与的公倍数中最小的正数称为b a 与的最小公倍数，记为],[b a .
最大公约数和最小公倍数的概念可以推广到有限多个整数的情形，
并用),,,(21n a a a 表示n a a a ,,,21 的最大公约数，],,,[21n a a a 表示
n a a a ,,,21 的最小公倍数.
若1),,,(21=n a a a ，则称n a a a a ,,,,321 互质，若n a a a ,,,21
中任何两个都互质，则称它们是两两互质的.注意，n 个整数互质与n
个整数两两互质是不同的概念，前者成立时后者不一定成立（例如，3，
15，8互质，但不两两互质）；显然后者成立时，前者必成立.
因为任何正数都不是0的倍数，所以在讨论最小公倍数时，一般
都假定这些整数不为0.同时，由于|||,|,b a b a 与有相同的公约数，且
|)||,(|),(b a b a =（有限多个亦成立），因此，我们总限于在自然数集
合内来讨论数的最大公约数和最小公倍数.
显然，若b a ,的标准分解式为i n
i i n
i i
p p b p
a i i
(,1
1
∏∏====βα为质数，i i a β,为非负整数）
，则
∏==n
i i i i p b a 1),min(),(βα ①
∏==n
i man i i i p b a 1
),(],[βα ②
例如 3960=23·32·5·11，
756=22·33·7，
则 （3960，756）=22·32=36，
[3960，756]=23·33·5·7·11=83160.
求最大公约数也可以用辗转相除法，其理论依据是：
定理二：设a 、b 、c 是三个不全为0的整数，且有整数t 使得c
bt a +=，则a 、b 与b 、c 有相同的公约数，因而),(),(c b b a =，
即).,(),(bt a b b a -=
因为，若a d 是、b 的任一公约数，则由b d c d c bt a b d a d
是即知和,||,|+=、c 的公约数；反之，若b d 是、c 的任一公约数，a d
也是、b 的公约数.
辗转相除法：设a 、b a N b >∈*且,， 由带余除法有
=+=<<+=<<+=<<+=+++----.0,,0,,0,,
0,1111n n n n n n n n n n n r r q r r r r r q r r r r
r q r b b r r bq a ③ 因为每进行一次带余除法，余数至少减1，即
11+>>>>n n r r r b ，而b 为有限数，因此，必有一个最多不超过b
的正整数n 存在，使得0≠n r ，而01=+n r ，故由定理二得：
).,(),,(),(),(11211b a b r r r r r r r r n n n n n ======-+（）
例如，（3960，756）=（756，180）=（180，36）=36. 具体
算式如下：
5（q 1） 3960（a ） 756（b ） 4（q 2） 3780 720
180（r 1） 36（r 2） 5（q 3） 180
0（r 3）
由定义和上述求法不难得出最大公约数和最小公倍数的如下性质：
（1）),(),(,b a m bm am N m =∈则. （2）设b a c ,为的公约数，
则.),(),(c b a c b c a =
特别地，若1),(),,(==c
b
c a b a c 则. （3）设n a a a ,,,21 是任意n 个正整数，如果n n
n c a c c a c c a a ===-),(,,),(,),(1332221 ， 则n n c a a a =),,,(21 .
因21121111|,|,|,|,|,|--------n n n n n n n n n n n n c c a c c c a
c c c a c 故而，如此类推得出n c 能整
除n n n c a a a 于是,,,,11 -是它们的一个公约数.又设n a a a
c ,,,21 为的任一公约数，则
21|,|a c a c ，因而2|c c ，同理可推出3|c c ，如此类推最后可得
n c c |. 于是n c c c ≤≤||，故
n c 是最大公约数.
（4）若c b a =),(，则一定有整数y x 和，使得c by ax =+. 特别
地，?=1),(b a 存在1,=+by ax y x 使得. 这可由辗转相除法的③式逆推
而得by ax r c n +==. （5）若),(),(,1),(b c b ac b a ==则. （6）*∈N
b a , ①)(]
,[],[*∈=N k b a k bk ak ；
②b a m ,为的任一公倍数，则m b a |],[；
③ab b a b a =],)[,(，特别地，若ab b a b a ==],[,1),(则.
①可由③直接得到，②可由最小公倍数定义得，③根据①、②式
知，
=],)[,(b a b a
∏∏==+==n
i n
i i i i i
ab p p
i i 1
1
),min(βαβα.
（7）设n a a a ,,,21 是任意n 个正整数.若
===-],[,,],[,],[1332221n n a m m a m m a a m n ，则n n m a a a
=],,,[21 .
这是一个求多个整数的最小公倍数的方法.它可用证明③类似的方
法来证明.
Ⅲ.方幂问题 一个正整数n 能否表成m 个整数的k 次方和的问题
称为方幂和问题.特别地，当1=m 时称为k 次方问题，当2=k 时，称
为平方和问题. 能表为某整数的平方的数称为完全平方数.简称平方数，
关于平方数，明显有如下一些简单的性质和结论： （1）平方数的个
位数字只可能是0，1，4，5，6，9. （2）偶数的平方数是4的倍数，
奇数的平方数被8除余1，即任何平方数被4除的余数
只能是0或1. （3）奇数平方的十位数字是偶数. （4）十位数字
是奇数的平方数的个位数一定是6. （5）不能被3整除的数的平方被3
除余1，能被3整除的数的平方能被3整除.因而，平方数被9除的余
数为0，1，4，7，且此平方数的各位数字的和被9除的余数也只能为
0，1，4，7. （6）平方数的约数的个数为奇数. （7）任何四个连续整
数的乘积加1，必定是一个平方数. 进一步研究可得到有关平方和的几
个结论: 定理三：奇素数p 能表示成两个正整数的平方和的充要条件
是.14+=m p
定理四：设正整数p m n 2=，其中p 不再含平方因数，n 能表示
成两个整数的平方的充
要条件是p 没有形如34+q 的质因数.
定理五：每个正整数都能表示成四个整数的平方和. 这几个定理的
证明略.这里重点是介绍有关k 方幂的解法技巧.k 方幂中许多问题实质
上是不定方程的整数解问题，比如著名的勾股数问题.
赛题精讲
例1：证明：对于任何自然数n 和k ，数1042),(3++=k k
n n
k n f 都不能分解成若干
个连续的正整数之积.
（1981年全国高中联赛试题）
【证明】由性质9知，只需证明数),(k n f 不能被一个很小的自然
数n 整除.因
,1)1)(1()3(31033),(333++--++=++-+=k k k k k k k k k n n n n
n n n n n k n f
),1)(1(|3),3(3|33+-++k k k k k n n n n n 3 1，故3 ),(k n f ，因
而),(k n f 不能分解成三
个或三个以上的连续自然数的积. 再证),(k n f 不能分解成两个连续
正整数的积.
由上知，)(13),(N q q k n f ∈+=，因而只需证方程：)1(13+=+x
x q 无正整数解.而
这一点可分别具体验算234,134,3++=r x 时，)1(+x x 均不是
13+q 形的数来说明. 故),(k n f 对任何正整数n 、k 都不能分解成若干
个连续正整数之积.
例2： 设p 和q 均为自然数,使得
.1319
+--+-= q p 证明：p 可被1979整除. (第21届
IMO 试题)
【证明】
)1318
1
4121(2)1319131211(+++-+++= q p =)6591
211()1319131211(+++-++++
=)990
19891()131816611()131916601(
++++++ =1979×)990
9891
96601(
++?+? 两端同乘以1319！得1319！*).(1979N m m q
p
∈?=?
此式说明1979|1319！×.p 由于1979为质数，且1979 1319！，
故1979|.p 【评述】把1979换成形如23+k 的质数，1319换成
*)(12N k k ∈+，命题仍成立.
牛顿二项式定理和n b a b a b a b a n
n
n
n
(|)(,|)(-+--为偶数), n b a b a n
n
(|)(-+为
奇数)在整除问题中经常用到.
例3 ：对于整数n 与k ，定义,),(1
1
2∑=-=
n
r k r
k n F 求证：)1,(n F 可整除).,(k n F
（1996加拿大数学竞赛试题）
【证明】当m n 2=时，,)12()1,2(21
∑=+==
m
r m m r m F
∑∑+=-=-+
=m
m r k m
r k r
r
k m F 211
211
2),2(
],
)12([)12(121
121
1
211
2-=-=-=--++=-++=∑∑∑k m
r k m
r k m
r k r m r r m r
由于[…]能被12)12(+=-++m r m r 整除，所以),2(k m F 能被
12+m 整除，另一方
面，
=
),2(k m F ,)2(])2([1212121
1
1
2----=-++-+∑k k k m r k m m r m r
上式中[…]能被m r m r 2)2(=-+整除，所以),2(k m F 也能被m
整除.因m 与2m +1
互质，所以),2(k m F 能被m （2m +1）（即)1,(m F ）整除.
类似可证当12+=m n 时，F （2m +1，k ）能被F （2m +1,1）
整除. 故),(k n F 能被
)1,(n F 整除.
例4 ：求一对整数b a ,，满足：(1))(b a ab +不能被7整除；
（2）777)(b a b a --+能
被77整除. (第25届IMO 试题)
【解】777)(b a b a --+=)](5)(3)[(7223355b a b a b a ab b a ab
+++++
=.))((7222ab b a b a ab +++ 根据题设要求(1)(2)知，
|,)(|72226ab b a ++即.|7223ab b a ++
令,7322=++ab b a 即,343)(2
=-+ab b a 即19=+b a ，则.343192-=ab 故可令
1,18==b a 即合要求.
(第15届美国普特南数学竞赛试题)
【评述】数学归纳法在整除问题中也有广泛应用. 例5：是否存在
1000000个连续整数，使得每一个都含有重复的素因子，即都能被某
个素数的平方所整除？ 【解】存在.用数学归纳法证明它的加强命题：
对任何正整数,m 存在m 个连续的整数，使得每一个都含有重复的素因
子. 当m =1时，显然成立.这只需取一个素数的平方.
假设当m =k 时命题成立,即有k 个连续整数k n n n +++,,2,1 ,它
们分别含有重复的
素因子k p p p ,,,21 ,任取一个与k p p p ,,,21 都不同的素数1+k
p (显然存在),当
21,2,1+=k p t 时,)1(22221+++k n p p tp k 这2
1+k p 个数中任两个数的差是形如)11(2122221-≤≤+k k p a p p
ap 的数,不能被21+k p 整除,故这21+k p 个数除以2
1+k p 后,余数两两不
同.但除以21+k p 后的余数只有0，1，…，21+k p －1这21+k
p 个，从而恰有一个数)1(2
100+≤≤k p t t ，使)1(222210+++k n p p p t k 能被21+k p 整
除.这时，
（)1+k 个连续整数：
,1222210++n p p p t k ++n p p p t k 222210 2，…，++n p p
p t k 2
22210 k ，
++n p p p t k 222210 （k +1）
分别能被2
122221,,+k k p p p p 整除，即
1+=k m 时命题成立.故题对一切正整数m 均成立.
例6：求证：.)
,)(,)(,(),,(],][,][,[],,[2
2a c c b b a c b a a c c b b a c b a =
（第1届美国数学奥林匹克竞赛试题）
【证明】设,,,1
1
1
∏∏∏======
n
i i n i i n i i i p c i p b i p a γβα其中
i p 为质数，i i i γβα,,为非负整数，则
∏==
n
i i
i i i p
c b a 1
),,max(,],,[γβα
∏==n
i i i i p b a 1
),max(,],[ βα
∏=∏
=n
i i
i i i p
c b a 1
),,m i n (,),,(γβα
∏==n
i i
i i p
b a 1
),min(,),( βα
因此只需证明
2max(),max(),max(),max(),,i i i i i i i i i αγγββαγβα---
=2min(),min(),min(),min(),,i i i i i i i i i αγγββαγβα---
上式关于i i i γβα,,对称，则不妨设i i i γβα≥≥，于是上式变为：
.22i i i i i i i i γγβγαβαα---=---此式显然成立，故得证.
例7：设a 和b 是两个正整数，p b a ,1),(=为大于或等于3的质
数，
b
a b a b a c p
p +++=,(），试证：（1）1),(=a c ；（2）1=c 或.p c =（1985
新加坡数学竞赛试题）
【证明】由已知得),(,
N s t cs b
a b a ct b a p
p ∈=++=+，两式相乘得,)(1112ct pa t pac t c a ct a b a st c p
p p p p p p p p ---++-=-+=+= 于是
,12211-----++-=p p p p p pa t pac t c cs 故.|1-p pa c
（1）现用反证法来证明1),(=a c .若,1),(>=k a c 令q 是k 的一个
质因子，则有
.|,|a q c q 因b a c +|，则b a q +|，从而.|b q 于是q 是a 、b 的
一个公约数，这与),(b a =1
矛盾，故1),(=a c .
（2）因为,1),(,|1=-a c pa c p 所以.|p c 而p 为质数且3≥p ，故
1=c 或.p c = 例8：设∑=+=
n
k n k k
S 1
75
)(，求最大公约数).,(3n n S S d =（第26届IMO 预选题）
【解】能过具体计算可猜想
.)2
)1((
2)21(24
4+=+++=n n n S n 此式不难用数学归纳法获证. 为求),(3n n S S
d =，对n 分奇偶来讨论. （1）当k n 2=时，
).)16(812,)12(2()]2
)16(6[2,]2)12(2[
2(44444
4+?+=++=k k k k k k k k d 由于12+k
和16+k 互质，所以).81,)12((24
4+=k k d 而当13+=t k 时
13,)12(81)12(4
4
+≠+=+t k t k 时，4
)12(+k 与81互质.故此时有
≥++==+==??=?=.)0(4666,812;26,88444
t t t n n k t n n n k d 时或当时当
（2）当当12+=k n 时).)23)(12(3[2,)]1)(12[(2(4
4++++=k k k k d
1,1223+++k k k 与因与质，所以).3,)1(()12(2444++=k k k 而当
23+=t k 时，
23),1(31+≠+=+k k t k 时，1+k 与34互质.故此时有
++==++==?=?+=.
)36162)12(2;56,162323)12(24
44
444时或当时当t t n n k t n n n k d
例9：m 盒子中各若干个球，每一次在其中)(m n n <个盒中加一
球.求证：不论开始的
分布情况如何，总可按上述方法进行有限次加球后使各盒中球数
相等的充要条件是
.1),(=n m （第26届IMO 预选题）
【证明】设1),(=n m ，则有Z v u ∈,使得)1()1(1++-=+=v m v
vm un ，此式说明：
对盒子连续加球u 次，可使1-m 个盒子各增加了v 个，一个增
加)1(+v 个.这样可将多增加了一个球的盒子选择为原来球数最少的那
个，于是经过u 次加球之后，原来球数最多的盒子
中的球与球数最少的盒子中的球数之差减少1，因此，经过有限次
加球后，各盒球数差为0，达到各盒中的球数相等.
用反证法证明必要性.若1),(>=d n m ，则只要在m 个盒中放
1+m 个球，则不管加球
多少次，例如，加球k 次，则这时m 个盒中共有球kn m ++1
（个），因为,1,|,|>d n d m d 所以kn m ++1不可能是d 的倍数，更
不是m 的倍数，各盒中的球决不能一样多，因此，必须1),(=n m .
例10：求所有这样的自然数n ，使得n
22211
8
++是一个自然数的平方.
（1980年第6届全俄数学竞赛试题）
【证明】（1）当8≤n 时，)122(222118118++?++=--n
n n N ，因（…）为奇数，所
以要使N 为平方数，n 必为偶数.逐一验证8,6,4,2=n 知，N 都不
是平方数. （2）当9=n 时，1122228
9118?=++=N 不是平方数.
（3）当10≥n 时，)2
9(28
8-+=n N ，要N 为平方数，829-+n 应为奇数的平方，不
妨假设8
29-+n =2)12(+k ,则).2()1(2
10
+?-=-k k n 由于1-k 和2+k 是一奇一偶，左边
为2的幂，因而只能1-k =1，于是得2=k ，由210
22
=-n 知12=n 为所求.
2024年11月2日发(作者：韩依云)
数学奥赛辅导第二讲整除
数学奥赛辅导 第二讲
整除
知识、方法、技能
整除是整数的一个重要内容，这里仅介绍其中的几个方面：整数
的整除性、最大公约数、最小公倍数、方幂问题.
Ⅰ. 整数的整除性
初等数论的基本研究对象是自然数集合及整数集合. 我们知道，整
数集合中可以作加、减、乘法运算，并且这些运算满足一些规律（即
加法和乘法的结合律和交换律，加法与乘法的分配律），但一般不能
做除法，即，如b a ,是整除，0≠b ，则b
a
不一定是整数. 由此引出初等数论中第一个基本概念：整数的整除
性.
定义一：（带余除法）对于任一整数a 和任一整数b ，必有惟一
的一对整数q ，r 使得
r bq a +=，b r <≤0，并且整数q 和r 由上述条件惟一确定，则
q 称为b 除a 的不完全商，
r 称为b 除a 的余数.
若0=r ，则称b 整除a ，或a 被b 整除，或称b a 是的倍数，或
称a b 是的约数（又叫因子），记为a b |.否则，b | a .
任何a 的非1,±±a 的约数，叫做a 的真约数. 0是任何整数的倍
数，1是任何整数的约数.
任一非零的整数是其本身的约数，也是其本身的倍数. 由整除的定
义，不难得出整除的如下性质： （1）若.|,|,|c a c b b a 则
（2）若.,,2,1,,|
,|1
n i Z c
b c a b a i
n
i i i i =∈∑=其中则
（3）若c a |，则.|cb ab 反之，亦成立.
（4）若||||,|b a b a ≤则.因此，若b a a b b a ±=则又,|,|. （5）
a 、b 互质，若.|,|,|c ab c b c a 则
（6）p 为质数，若,|21n a a a p 则p 必能整除n a a a ,,,21
中的某一个. 特别地，若p 为质数，.|,|a p a p n 则
（7）如在等式
∑∑===m
k k
n i i b
a 1
1
中除开某一项外，其余各项都是c 的倍数，则这一项也是c
的倍数.
（8）n 个连续整数中有且只有一个是n 的倍数. （9）任何n 个连
续整数之积一定是n 的倍数.
本讲开始在整除的定义同时给出了约数的概念，又由上一讲的算
术基本定理，我们就可以讨论整数的约数的个数了.
定理一：设大于1的整数a 的标准分解式为n n p p p p p p a n
<<
α
α
为质数，i α均为非负整数），则a 的约数的个数为
∏=+=n
i i a d 1
)1)(α（.
所有的约数和为：
∏
=+--=n
i i i p p a i 1
11
1
)(ασ.
事实上，由算术基本定理的推论知∏=+=
n
i i
a d 1
)1()(α
，而各约数的和就是
∏=+++n
i i i
i pa p
1
)1( 展开后的各项之和，所以
∏∏
==--=+++=n
i n
i i i i p p p p a i i
1111
1
)1()(αασ 例如，25200=24·32·52·7，所以
90)11)(12)(12)(14()25200(=++++=d ，
999441
71
72)25200(2335=--?--?--?--=σ.
Ⅱ. 最大公约数和最小公倍数
定义二：设a 、b 是两个不全为0的整数.若整数c 满足：b c a c
|,|，则称b a c ,为的公约数，b a 与的所有公约数中的最大者称为b a
与的最大公约数，记为),(b a .如果),(b a =1，则称b a 与互质或互素.
定义三：如果a d 是、b 的倍数，则称a d 是、b 的公倍数. b a
与的公倍数中最小的正数称为b a 与的最小公倍数，记为],[b a .
最大公约数和最小公倍数的概念可以推广到有限多个整数的情形，
并用),,,(21n a a a 表示n a a a ,,,21 的最大公约数，],,,[21n a a a 表示
n a a a ,,,21 的最小公倍数.
若1),,,(21=n a a a ，则称n a a a a ,,,,321 互质，若n a a a ,,,21
中任何两个都互质，则称它们是两两互质的.注意，n 个整数互质与n
个整数两两互质是不同的概念，前者成立时后者不一定成立（例如，3，
15，8互质，但不两两互质）；显然后者成立时，前者必成立.
因为任何正数都不是0的倍数，所以在讨论最小公倍数时，一般
都假定这些整数不为0.同时，由于|||,|,b a b a 与有相同的公约数，且
|)||,(|),(b a b a =（有限多个亦成立），因此，我们总限于在自然数集
合内来讨论数的最大公约数和最小公倍数.
显然，若b a ,的标准分解式为i n
i i n
i i
p p b p
a i i
(,1
1
∏∏====βα为质数，i i a β,为非负整数）
，则
∏==n
i i i i p b a 1),min(),(βα ①
∏==n
i man i i i p b a 1
),(],[βα ②
例如 3960=23·32·5·11，
756=22·33·7，
则 （3960，756）=22·32=36，
[3960，756]=23·33·5·7·11=83160.
求最大公约数也可以用辗转相除法，其理论依据是：
定理二：设a 、b 、c 是三个不全为0的整数，且有整数t 使得c
bt a +=，则a 、b 与b 、c 有相同的公约数，因而),(),(c b b a =，
即).,(),(bt a b b a -=
因为，若a d 是、b 的任一公约数，则由b d c d c bt a b d a d
是即知和,||,|+=、c 的公约数；反之，若b d 是、c 的任一公约数，a d
也是、b 的公约数.
辗转相除法：设a 、b a N b >∈*且,， 由带余除法有
=+=<<+=<<+=<<+=+++----.0,,0,,0,,
0,1111n n n n n n n n n n n r r q r r r r r q r r r r
r q r b b r r bq a ③ 因为每进行一次带余除法，余数至少减1，即
11+>>>>n n r r r b ，而b 为有限数，因此，必有一个最多不超过b
的正整数n 存在，使得0≠n r ，而01=+n r ，故由定理二得：
).,(),,(),(),(11211b a b r r r r r r r r n n n n n ======-+（）
例如，（3960，756）=（756，180）=（180，36）=36. 具体
算式如下：
5（q 1） 3960（a ） 756（b ） 4（q 2） 3780 720
180（r 1） 36（r 2） 5（q 3） 180
0（r 3）
由定义和上述求法不难得出最大公约数和最小公倍数的如下性质：
（1）),(),(,b a m bm am N m =∈则. （2）设b a c ,为的公约数，
则.),(),(c b a c b c a =
特别地，若1),(),,(==c
b
c a b a c 则. （3）设n a a a ,,,21 是任意n 个正整数，如果n n
n c a c c a c c a a ===-),(,,),(,),(1332221 ， 则n n c a a a =),,,(21 .
因21121111|,|,|,|,|,|--------n n n n n n n n n n n n c c a c c c a
c c c a c 故而，如此类推得出n c 能整
除n n n c a a a 于是,,,,11 -是它们的一个公约数.又设n a a a
c ,,,21 为的任一公约数，则
21|,|a c a c ，因而2|c c ，同理可推出3|c c ，如此类推最后可得
n c c |. 于是n c c c ≤≤||，故
n c 是最大公约数.
（4）若c b a =),(，则一定有整数y x 和，使得c by ax =+. 特别
地，?=1),(b a 存在1,=+by ax y x 使得. 这可由辗转相除法的③式逆推
而得by ax r c n +==. （5）若),(),(,1),(b c b ac b a ==则. （6）*∈N
b a , ①)(]
,[],[*∈=N k b a k bk ak ；
②b a m ,为的任一公倍数，则m b a |],[；
③ab b a b a =],)[,(，特别地，若ab b a b a ==],[,1),(则.
①可由③直接得到，②可由最小公倍数定义得，③根据①、②式
知，
=],)[,(b a b a
∏∏==+==n
i n
i i i i i
ab p p
i i 1
1
),min(βαβα.
（7）设n a a a ,,,21 是任意n 个正整数.若
===-],[,,],[,],[1332221n n a m m a m m a a m n ，则n n m a a a
=],,,[21 .
这是一个求多个整数的最小公倍数的方法.它可用证明③类似的方
法来证明.
Ⅲ.方幂问题 一个正整数n 能否表成m 个整数的k 次方和的问题
称为方幂和问题.特别地，当1=m 时称为k 次方问题，当2=k 时，称
为平方和问题. 能表为某整数的平方的数称为完全平方数.简称平方数，
关于平方数，明显有如下一些简单的性质和结论： （1）平方数的个
位数字只可能是0，1，4，5，6，9. （2）偶数的平方数是4的倍数，
奇数的平方数被8除余1，即任何平方数被4除的余数
只能是0或1. （3）奇数平方的十位数字是偶数. （4）十位数字
是奇数的平方数的个位数一定是6. （5）不能被3整除的数的平方被3
除余1，能被3整除的数的平方能被3整除.因而，平方数被9除的余
数为0，1，4，7，且此平方数的各位数字的和被9除的余数也只能为
0，1，4，7. （6）平方数的约数的个数为奇数. （7）任何四个连续整
数的乘积加1，必定是一个平方数. 进一步研究可得到有关平方和的几
个结论: 定理三：奇素数p 能表示成两个正整数的平方和的充要条件
是.14+=m p
定理四：设正整数p m n 2=，其中p 不再含平方因数，n 能表示
成两个整数的平方的充
要条件是p 没有形如34+q 的质因数.
定理五：每个正整数都能表示成四个整数的平方和. 这几个定理的
证明略.这里重点是介绍有关k 方幂的解法技巧.k 方幂中许多问题实质
上是不定方程的整数解问题，比如著名的勾股数问题.
赛题精讲
例1：证明：对于任何自然数n 和k ，数1042),(3++=k k
n n
k n f 都不能分解成若干
个连续的正整数之积.
（1981年全国高中联赛试题）
【证明】由性质9知，只需证明数),(k n f 不能被一个很小的自然
数n 整除.因
,1)1)(1()3(31033),(333++--++=++-+=k k k k k k k k k n n n n
n n n n n k n f
),1)(1(|3),3(3|33+-++k k k k k n n n n n 3 1，故3 ),(k n f ，因
而),(k n f 不能分解成三
个或三个以上的连续自然数的积. 再证),(k n f 不能分解成两个连续
正整数的积.
由上知，)(13),(N q q k n f ∈+=，因而只需证方程：)1(13+=+x
x q 无正整数解.而
这一点可分别具体验算234,134,3++=r x 时，)1(+x x 均不是
13+q 形的数来说明. 故),(k n f 对任何正整数n 、k 都不能分解成若干
个连续正整数之积.
例2： 设p 和q 均为自然数,使得
.1319
+--+-= q p 证明：p 可被1979整除. (第21届
IMO 试题)
【证明】
)1318
1
4121(2)1319131211(+++-+++= q p =)6591
211()1319131211(+++-++++
=)990
19891()131816611()131916601(
++++++ =1979×)990
9891
96601(
++?+? 两端同乘以1319！得1319！*).(1979N m m q
p
∈?=?
此式说明1979|1319！×.p 由于1979为质数，且1979 1319！，
故1979|.p 【评述】把1979换成形如23+k 的质数，1319换成
*)(12N k k ∈+，命题仍成立.
牛顿二项式定理和n b a b a b a b a n
n
n
n
(|)(,|)(-+--为偶数), n b a b a n
n
(|)(-+为
奇数)在整除问题中经常用到.
例3 ：对于整数n 与k ，定义,),(1
1
2∑=-=
n
r k r
k n F 求证：)1,(n F 可整除).,(k n F
（1996加拿大数学竞赛试题）
【证明】当m n 2=时，,)12()1,2(21
∑=+==
m
r m m r m F
∑∑+=-=-+
=m
m r k m
r k r
r
k m F 211
211
2),2(
],
)12([)12(121
121
1
211
2-=-=-=--++=-++=∑∑∑k m
r k m
r k m
r k r m r r m r
由于[…]能被12)12(+=-++m r m r 整除，所以),2(k m F 能被
12+m 整除，另一方
面，
=
),2(k m F ,)2(])2([1212121
1
1
2----=-++-+∑k k k m r k m m r m r
上式中[…]能被m r m r 2)2(=-+整除，所以),2(k m F 也能被m
整除.因m 与2m +1
互质，所以),2(k m F 能被m （2m +1）（即)1,(m F ）整除.
类似可证当12+=m n 时，F （2m +1，k ）能被F （2m +1,1）
整除. 故),(k n F 能被
)1,(n F 整除.
例4 ：求一对整数b a ,，满足：(1))(b a ab +不能被7整除；
（2）777)(b a b a --+能
被77整除. (第25届IMO 试题)
【解】777)(b a b a --+=)](5)(3)[(7223355b a b a b a ab b a ab
+++++
=.))((7222ab b a b a ab +++ 根据题设要求(1)(2)知，
|,)(|72226ab b a ++即.|7223ab b a ++
令,7322=++ab b a 即,343)(2
=-+ab b a 即19=+b a ，则.343192-=ab 故可令
1,18==b a 即合要求.
(第15届美国普特南数学竞赛试题)
【评述】数学归纳法在整除问题中也有广泛应用. 例5：是否存在
1000000个连续整数，使得每一个都含有重复的素因子，即都能被某
个素数的平方所整除？ 【解】存在.用数学归纳法证明它的加强命题：
对任何正整数,m 存在m 个连续的整数，使得每一个都含有重复的素因
子. 当m =1时，显然成立.这只需取一个素数的平方.
假设当m =k 时命题成立,即有k 个连续整数k n n n +++,,2,1 ,它
们分别含有重复的
素因子k p p p ,,,21 ,任取一个与k p p p ,,,21 都不同的素数1+k
p (显然存在),当
21,2,1+=k p t 时,)1(22221+++k n p p tp k 这2
1+k p 个数中任两个数的差是形如)11(2122221-≤≤+k k p a p p
ap 的数,不能被21+k p 整除,故这21+k p 个数除以2
1+k p 后,余数两两不
同.但除以21+k p 后的余数只有0，1，…，21+k p －1这21+k
p 个，从而恰有一个数)1(2
100+≤≤k p t t ，使)1(222210+++k n p p p t k 能被21+k p 整
除.这时，
（)1+k 个连续整数：
,1222210++n p p p t k ++n p p p t k 222210 2，…，++n p p
p t k 2
22210 k ，
++n p p p t k 222210 （k +1）
分别能被2
122221,,+k k p p p p 整除，即
1+=k m 时命题成立.故题对一切正整数m 均成立.
例6：求证：.)
,)(,)(,(),,(],][,][,[],,[2
2a c c b b a c b a a c c b b a c b a =
（第1届美国数学奥林匹克竞赛试题）
【证明】设,,,1
1
1
∏∏∏======
n
i i n i i n i i i p c i p b i p a γβα其中
i p 为质数，i i i γβα,,为非负整数，则
∏==
n
i i
i i i p
c b a 1
),,max(,],,[γβα
∏==n
i i i i p b a 1
),max(,],[ βα
∏=∏
=n
i i
i i i p
c b a 1
),,m i n (,),,(γβα
∏==n
i i
i i p
b a 1
),min(,),( βα
因此只需证明
2max(),max(),max(),max(),,i i i i i i i i i αγγββαγβα---
=2min(),min(),min(),min(),,i i i i i i i i i αγγββαγβα---
上式关于i i i γβα,,对称，则不妨设i i i γβα≥≥，于是上式变为：
.22i i i i i i i i γγβγαβαα---=---此式显然成立，故得证.
例7：设a 和b 是两个正整数，p b a ,1),(=为大于或等于3的质
数，
b
a b a b a c p
p +++=,(），试证：（1）1),(=a c ；（2）1=c 或.p c =（1985
新加坡数学竞赛试题）
【证明】由已知得),(,
N s t cs b
a b a ct b a p
p ∈=++=+，两式相乘得,)(1112ct pa t pac t c a ct a b a st c p
p p p p p p p p ---++-=-+=+= 于是
,12211-----++-=p p p p p pa t pac t c cs 故.|1-p pa c
（1）现用反证法来证明1),(=a c .若,1),(>=k a c 令q 是k 的一个
质因子，则有
.|,|a q c q 因b a c +|，则b a q +|，从而.|b q 于是q 是a 、b 的
一个公约数，这与),(b a =1
矛盾，故1),(=a c .
（2）因为,1),(,|1=-a c pa c p 所以.|p c 而p 为质数且3≥p ，故
1=c 或.p c = 例8：设∑=+=
n
k n k k
S 1
75
)(，求最大公约数).,(3n n S S d =（第26届IMO 预选题）
【解】能过具体计算可猜想
.)2
)1((
2)21(24
4+=+++=n n n S n 此式不难用数学归纳法获证. 为求),(3n n S S
d =，对n 分奇偶来讨论. （1）当k n 2=时，
).)16(812,)12(2()]2
)16(6[2,]2)12(2[
2(44444
4+?+=++=k k k k k k k k d 由于12+k
和16+k 互质，所以).81,)12((24
4+=k k d 而当13+=t k 时
13,)12(81)12(4
4
+≠+=+t k t k 时，4
)12(+k 与81互质.故此时有
≥++==+==??=?=.)0(4666,812;26,88444
t t t n n k t n n n k d 时或当时当
（2）当当12+=k n 时).)23)(12(3[2,)]1)(12[(2(4
4++++=k k k k d
1,1223+++k k k 与因与质，所以).3,)1(()12(2444++=k k k 而当
23+=t k 时，
23),1(31+≠+=+k k t k 时，1+k 与34互质.故此时有
++==++==?=?+=.
)36162)12(2;56,162323)12(24
44
444时或当时当t t n n k t n n n k d
例9：m 盒子中各若干个球，每一次在其中)(m n n <个盒中加一
球.求证：不论开始的
分布情况如何，总可按上述方法进行有限次加球后使各盒中球数
相等的充要条件是
.1),(=n m （第26届IMO 预选题）
【证明】设1),(=n m ，则有Z v u ∈,使得)1()1(1++-=+=v m v
vm un ，此式说明：
对盒子连续加球u 次，可使1-m 个盒子各增加了v 个，一个增
加)1(+v 个.这样可将多增加了一个球的盒子选择为原来球数最少的那
个，于是经过u 次加球之后，原来球数最多的盒子
中的球与球数最少的盒子中的球数之差减少1，因此，经过有限次
加球后，各盒球数差为0，达到各盒中的球数相等.
用反证法证明必要性.若1),(>=d n m ，则只要在m 个盒中放
1+m 个球，则不管加球
多少次，例如，加球k 次，则这时m 个盒中共有球kn m ++1
（个），因为,1,|,|>d n d m d 所以kn m ++1不可能是d 的倍数，更
不是m 的倍数，各盒中的球决不能一样多，因此，必须1),(=n m .
例10：求所有这样的自然数n ，使得n
22211
8
++是一个自然数的平方.
（1980年第6届全俄数学竞赛试题）
【证明】（1）当8≤n 时，)122(222118118++?++=--n
n n N ，因（…）为奇数，所
以要使N 为平方数，n 必为偶数.逐一验证8,6,4,2=n 知，N 都不
是平方数. （2）当9=n 时，1122228
9118?=++=N 不是平方数.
（3）当10≥n 时，)2
9(28
8-+=n N ，要N 为平方数，829-+n 应为奇数的平方，不
妨假设8
29-+n =2)12(+k ,则).2()1(2
10
+?-=-k k n 由于1-k 和2+k 是一奇一偶，左边
为2的幂，因而只能1-k =1，于是得2=k ，由210
22
=-n 知12=n 为所求.