数学奥赛辅导 第二讲 整 除

数学奥赛辅导 第二讲

整除

知识、方法、技能

整除是整数的一个重要内容，这里仅介绍其中的几个方面：整数的整除性、最大公约数、最小公倍数、方幂问题.

Ⅰ. 整数的整除性

初等数论的基本研究对象是自然数集合及整数集合. 我们知道，整数集合中可以作加、减、乘法运算，并且这些运算满足一些规律（即加法和乘法的结合律和交换律，加法与乘法的分配律），但一般不能做除法，即，如a,b是整除，b?0，则初等数论中第一个基本概念：整数的整除性.

定义一：（带余除法）对于任一整数a和任一整数b，必有惟一的一对整数q，r使得

a不一定是整数. 由此引出ba?bq?r，0?r?b，并且整数q和r由上述条件惟一确定，则q称为b除a的不完全商，

r称为b除a的余数.

若r?0，则称b整除a，或a被b整除，或称a是b的倍数，或称b是a的约数（又叫因子），记为b|a.否则，b| a.

任何a的非?a,?1的约数，叫做a的真约数. 0是任何整数的倍数，1是任何整数的约数.

任一非零的整数是其本身的约数，也是其本身的倍数. 由整除的定义，不难得出整除的如下性质： （1）若a|b,b|c,则a|c.

（2）若a|bi,则a|?cb,其中ciii?1ni?Z,i?1,2,?,n.

（3）若a|c，则ab|cb.反之，亦成立.

（4）若a|b,则|a|?|b|.因此，若a|b,又b|a,则a??b. （5）a、b互质，若a|c,b|c,则ab|c.

1

（6）p为质数，若p|a1?a2???an,则p必能整除a1,a2,?,an中的某一个. 特别地，若p为质数，p|an,则p|a.

（7）如在等式

?a??bii?1k?1nmk中除开某一项外，其余各项都是c的倍数，则这一项也是c的倍数.

（8）n个连续整数中有且只有一个是n的倍数. （9）任何n个连续整数之积一定是n的倍数.

本讲开始在整除的定义同时给出了约数的概念，又由上一讲的算术基本定理，我们就可以讨论整数的约数的个数了.

定理一：设大于1的整数a的标准分解式为a?p11?p2?pnn(p1?p2???pn为质数，?i均为非负整数），则a的约数的个数为

???d(a)??（?i?1).

i?1n所有的约数和为：

?(a)??i?1npi?i?1?1.

pi?1事实上，由算术基本定理的推论知d(a)??(?i?1ni?1)，而各约数的和就是

?(1?pi?1ni???paii)展开后的各项之和，所以

nn?ip1?1 ?(a)??(1?pi???pi)??i?1i?1pi?1?i例如，25200=24·32·52·7，所以

d(25200)?(4?1)(2?1)(2?1)(1?1)?90，

25?133?153?172?1?(25200)?????99944.

2?13?15?17?1Ⅱ. 最大公约数和最小公倍数

2

定义二：设a、b是两个不全为0的整数.若整数c满足：c|a,c|b，则称c为a,b的公约数，a与b的所有公约数中的最大者称为a与b的最大公约数，记为(a,b).如果(a,b)=1，则称a与b互质或互素.

定义三：如果d是a、b的倍数，则称d是a、b的公倍数. a与b的公倍数中最小的正数称为a与b的最小公倍数，记为[a,b].

最大公约数和最小公倍数的概念可以推广到有限多个整数的情形，并用(a1,a2,?,an)表示a1,a2,?,an的最大公约数，[a1,a2,?,an]表示a1,a2,?,an的最小公倍数.

若(a1,a2,?,an)?1，则称a1,a2,a3,?,an互质，若a1,a2,?,an中任何两个都互质，则称它们是两两互质的.注意，n个整数互质与n个整数两两互质是不同的概念，前者成立时后者不一定成立（例如，3，15，8互质，但不两两互质）；显然后者成立时，前者必成立.

因为任何正数都不是0的倍数，所以在讨论最小公倍数时，一般都假定这些整数不为0.同时，由于a,b与|a|,|b|有相同的公约数，且(a,b)?(|a|,|b|)（有限多个亦成立），因此，我们总限于在自然数集合内来讨论数的最大公约数和最小公倍数.

显然，若a,b的标准分解式为a?则

?pi?1ni?i，,b??pi?i(pi为质数，ai,?i为非负整数）

i?1n(a,b)??pimin(?i,?i) ①

i?1nn[a,b]??piman(?i,?i) ②

i?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使得a?bt?c，则a、b与b、c有相同的公约数，因而(a,b)?(b,c)，即(a,b)?(b,a?bt).

3

因为，若d是a、b的任一公约数，则由d|a,d|b和a?bt?c知d|c,即d是b、c的公约数；反之，若d是b、c的任一公约数，d也是a、b的公约数.

辗转相除法：设a、b?N?,且a?b， 由带余除法有

??b?r1q2?r2,0?r2?r1,????? ③ rn?2?rn?1qn?rn,0?rn?rn?1,??rn?1?rnqn?1?rn?1,rn?1?0.??因为每进行一次带余除法，余数至少减1，即b?r1???rn?rn?1，而b为有限数，因此，必有一个最多不超过b的正整数n存在，使得rn?0，而rn?1?0，故由定理二得：

a?bq1?r1,0?r1?b,rn?(rn?1,rn)?(rn,rn?1)???(r2,r1）?（r1,b)?(a,b).

例如，（3960，756）=（756，180）=（180，36）=36. 具体算式如下：

5（q1） 3960（a） 756（b） 4（q2） 3780 720

180（r1） 36（r2） 5（q3） 180

0（r3）

由定义和上述求法不难得出最大公约数和最小公倍数的如下性质： （1）m?N,则(am,bm)?m(a,b). （2）设c为a,b的公约数，则(,)?abcc(a,b)ab.特别地，若c?(a,b),则(,)?1. ccc（3）设a1,a2,?,an是任意n个正整数，如果(a1,a2)?c2,(c2,a3)?c3,?,(cn?1,an)?cn， 则(a1,a2,?,an)?cn.

因cn|an,cn|cn?1,而cn?1|an?1,cn?1|cn?2,故cn?1|an?1,cn|cn?2，如此类推得出cn能整

4

除an,an?1,?,a1,于是cn是它们的一个公约数.又设c为a1,a2,?,an的任一公约数，则

c|a1,c|a2，因而c|c2，同理可推出c|c3，如此类推最后可得c|cn. 于是c?|c|?cn，故

cn是最大公约数.

（4）若(a,b)?c，则一定有整数x和y，使得ax?by?c. 特别地，(a,b)?1?存在x,y使得ax?by?1. 这可由辗转相除法的③式逆推而得c?rn?ax?by. （5）若(a,b)?1,则(ac,b)?(c,b). （6）a,b?N? ①[ak,bk]?k[a,b](k?N?)；

②m为a,b的任一公倍数，则[a,b]|m；

③(a,b)[a,b]?ab，特别地，若(a,b)?1,则[a,b]?ab.

①可由③直接得到，②可由最小公倍数定义得，③根据①、②式知，

(a,b)[a,b]?

?pi?1nimin(?i,?i)??pi?i??i?ab.

i?1n（7）设a1,a2,?,an是任意n个正整数.若[a1,a2]?m2,[m2,a3]?m3,?,[mn?1,an]?mn，则[a1,a2,?,an]?mn.

这是一个求多个整数的最小公倍数的方法.它可用证明③类似的方法来证明.

Ⅲ.方幂问题 一个正整数n能否表成m个整数的k次方和的问题称为方幂和问题.特别地，当m?1时称为k次方问题，当k?2时，称为平方和问题. 能表为某整数的平方的数称为完全平方数.简称平方数，关于平方数，明显有如下一些简单的性质和结论： （1）平方数的个位数字只可能是0，1，4，5，6，9. （2）偶数的平方数是4的倍数，奇数的平方数被8除余1，即任何平方数被4除的余数

5

只能是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能表示成两个正整数的平方和的充要条件是p?4m?1.

定理四：设正整数n?m2p，其中p不再含平方因数，n能表示成两个整数的平方的充

要条件是p没有形如4q?3的质因数.

定理五：每个正整数都能表示成四个整数的平方和. 这几个定理的证明略.这里重点是介绍有关k方幂的解法技巧.k方幂中许多问题实质上是不定方程的整数解问题，比如著名的勾股数问题.

赛题精讲

例1：证明：对于任何自然数n和k，数f(n,k)?2n3k?4nk?10都不能分解成若干

（1981年全国高中联赛试题）

个连续的正整数之积.

【证明】由性质9知，只需证明数f(n,k)不能被一个很小的自然数n整除.因

f(n,k)?3n3k?3nk?n3k?nk?10?3(n3k?nk?3)?nk(nk?1)(nk?1)?1,

3|3(n3k?nk?3),3|nk(nk?1)(nk?1),3 1，故3 f(n,k)，因而f(n,k)不能分解成三

个或三个以上的连续自然数的积.

再证f(n,k)不能分解成两个连续正整数的积.

由上知，f(n,k)?3q?1(q?N)，因而只需证方程：3q?1?x(x?1)无正整数解.而

这一点可分别具体验算x?3r,34?1,34?2时，x(x?1)均不是3q?1形的数来说明.

故f(n,k)对任何正整数n、k都不能分解成若干个连续正整数之积. 例2： 设p和q均为自然数,使得

6

p1111?1??????. q2313181319证明：p可被1979整除. (第21届IMO试题) 【证明】

p111111?(1????)?2(????) q23131924131811111????)?(1????) 2313192659111111?)?(?)???(?) =(66013196611318989990111????) =1979×(660?1319661?1318989?990=(1? 两端同乘以1319！得1319！?p?1979?m(m?N*). 此式说明1979|1319！×p.由于q1979为质数，且1979 1319！，故1979|p.

【评述】把1979换成形如3k?2的质数，1319换成2k?1(k?N*)，命题仍成立. 牛顿二项式定理和(a?b)|a?b,(a?b)|a?b(n为偶数), (a?b)|a?b(n为

nnnnnn奇数)在整除问题中经常用到.

例3 ：对于整数n与k，定义F(n,k)??rr?1n2k?1,求证：F(n,1)可整除F(n,k).

（1996加拿大数学竞赛试题）

【证明】当n?2m时，F(2m,1)?m2m?r?m(2m?1),

r?12m

F(2m,k)??rr?1m2k?1?r?m?1m?r2k?1

??rr?1m2k?1??(2m?1?r)2k?1r?1

??[r2k?1?(2m?1?r)2k?1],r?1

由于[…]能被r?(2m?1?r)?2m?1整除，所以F(2m,k)能被2m?1整除，另一方

面，

7

F(2m,k)??[rr?1m?12k?1?(2m?r)2k?1]?m2k?1?(2m)2k?1,

上式中[…]能被r?(2m?r)?2m整除，所以F(2m,k)也能被m整除.因m与2m+1

互质，所以F(2m,k)能被m（2m+1）（即F(m,1)）整除.

类似可证当n?2m?1时，F（2m+1，k）能被F（2m+1,1）整除. 故F(n,k)能被

F(n,1)整除.

例4 ：求一对整数a,b，满足：(1)ab(a?b)不能被7整除；（2）(a?b)7?a7?b7能

被77整除. (第25届IMO试题)

【解】(a?b)7?a7?b7=7ab[(a5?b5)?3ab(a3?b3)?5a2b2(a?b)]

=7ab(a?b)(a2?b2?ab)2.

根据题设要求(1)(2)知，76|(a2?b2?ab)2|,即73|a2?b2?ab.

2232令a?b?ab?7,即(a?b)?ab?343,即a?b?19，则ab?192?343.故可令

a?18,b?1即合要求.

(第15届美国普特南数学竞赛试题)

【评述】数学归纳法在整除问题中也有广泛应用. 例5：是否存在1000000个连续整数，使得每一个都含有重复的素因子，即都能被某个素数的平方所整除？ 【解】存在.用数学归纳法证明它的加强命题：对任何正整数m,存在m个连续的整数，使得每一个都含有重复的素因子. 当m=1时，显然成立.这只需取一个素数的平方.

假设当m=k时命题成立,即有k个连续整数n?1,n?2,?,n?k,它们分别含有重复的

素因子p1,p2,?,pk,任取一个与p1,p2,?,pk都不同的素数pk?1(显然存在),当

22222时,这t?1,2,?pktpp?p?n?(k?1)p?112kk?1个数中任两个数的差是形如222222ap12p2?pk(1?a?pk)的数,不能被pk?1?1?1整除,故这pk?1个数除以pk?1后,余数两两不

8

2222同.但除以pk1，…，pk从而恰有一个数t0(1?t0?pk?1后的余数只有0，?1－1这pk?1个，?1)，2222使t0p1（k?1)个连续整数： p2?pk?n?(k?1)能被pk?1整除.这时，

222222t0p12p2?pk?n?1,t0p12p2?pk?n?2，…，t0p12p2?pk?n?k，

22t0p12p2?pk?n?（k+1）

2222m?k?1时命题成立.故题对一切正整数m均成立. 分别能被p1,p2?pk,pk?1整除，即

[a,b,c]2(a,b,c)2例6：求证：?.

[a,b][b,c][c,a](a,b)(b,c)(c,a)（第1届美国数学奥林匹克竞赛试题）

【证明】设a?

?pi?i,b??pi?i,c??pi?i,其中

i?1i?1i?1nnnpi为质数，?i,?i,?i为非负整数，则

[a,b,c]?n?pi?1nmax(?i,?i,?i)i,

[a,b]??pimax(?i,?i)?,

i?1

(a,b,c)??n?pi?1nmi?ni(,?i,?i)i,

(a,b)?

因此只需证明

?pi?1min(?i,?i)i?,

2max(?i,?i,?i)?max(?i,?i)?max(?i,?i)?max(?i,?i) =2min(?i,?i,?i)?min(?i,?i)?min(?i,?i)?min(?i,?i)

上式关于?i,?i,?i对称，则不妨设?i??i??i，于是上式变为：

2?i??i??i??i?2?i??i??i??i.此式显然成立，故得证.

例7：设a和b是两个正整数，(a,b)?1,p为大于或等于3的质数，

9

ap?bpc?(a?b,），试证：（1）(c,a)?1；（2）c?1或c?p.（1985新加坡数学竞赛试题）

a?bap?bp?cs(t,s?N)，两式相乘得 【证明】由已知得a?b?ct,a?bc2st?ap?bp?ap?(ct?a)p?cptp?pacp?1tp?1???pap?1ct,于是

cs?cp?1tp?1?pacp?2tp?2???pap?1,故c|pap?1.

（1）现用反证法来证明(c,a)?1.若(c,a)?k?1,令q是k的一个质因子，则有

q|c,q|a.因c|a?b，则q|a?b，从而q|b.于是q是a、b的一个公约数，这与(a,b)=1

矛盾，故(c,a)?1.

（2）因为c|pap?1,(c,a)?1,所以c|p.而p为质数且p?3，故c?1或c?p. 例8：设Sn??(kk?1n5?k7)，求最大公约数d?(Sn,S3n).（第26届IMO预选题）

【解】能过具体计算可猜想

Sn?2(1?2???n)4?2(n(n?1)4). 此式不难用数学归纳法获证. 2 为求d?(Sn,S3n)，对n分奇偶来讨论. （1）当n?2k时，

d?(2[

2k(2k?1)46k(6k?1)4],2[])?(2k4(2k?1)4,2?81k4(6k?1)4). 2244和6k?1互质，所以d?2k((2k?1),81).而当k?3t?1时

44由于2k?1

4 (2k?1)?81(2t?1),k?3t?1时，(2k?1)与81互质.故此时有

?n481442?81k?2?81?4?n,当n?6t?2时;??82 d?? ?2k4?1n4,当n?6t?6或6t?4时(t?0).?8?44（2）当当n?2k?1时d?(2[(2k?1)(k?1)],2[3(2k?1)(3k?2)).

10

因3k?2与2k?1,k?1与质，所以k?2(2k?1)4((k?1)4,34).而当k?3t?2时，

k?1?3(t?1),k?3k?2时，k?1与34互质.故此时有

4444??2(2k?1)?3?2n?3?162n,当n?6t?5时;d?? 44??2(2k?1)?2n当n?6t?1或6t?3时).

例9：m盒子中各若干个球，每一次在其中n(n?m)个盒中加一球.求证：不论开始的

分布情况如何，总可按上述方法进行有限次加球后使各盒中球数相等的充要条件是

(m,n)?1. （第26届IMO预选题）

【证明】设(m,n)?1，则有u,v?Z使得un?vm?1?v(m?1)?(v?1)，此式说明：

对盒子连续加球u次，可使m?1个盒子各增加了v个，一个增加(v?1)个.这样可将多增加了一个球的盒子选择为原来球数最少的那个，于是经过u次加球之后，原来球数最多的盒子

中的球与球数最少的盒子中的球数之差减少1，因此，经过有限次加球后，各盒球数差为0，达到各盒中的球数相等.

用反证法证明必要性.若(m,n)?d?1，则只要在m个盒中放m?1个球，则不管加球

多少次，例如，加球k次，则这时m个盒中共有球m?1?kn（个），因为d|m,d|n,d?1,所以m?1?kn不可能是d的倍数，更不是m的倍数，各盒中的球决不能一样多，因此，必须(m,n)?1.

例10：求所有这样的自然数n，使得2?2?2是一个自然数的平方.

（1980年第6届全俄数学竞赛试题）

811n8?n11?n【证明】（1）当n?8时，N?2?2?2?(2?2?1)，因（…）为奇数，所

811n以要使N为平方数，n必为偶数.逐一验证n?2,4,6,8知，N都不是平方数.

81198（2）当n?9时，N?2?2?2?2?11不是平方数.

（3）当n?10时，N?2(9?2n?88n?8)，要N为平方数，9?2n?8应为奇数的平方，不

妨假设9?2=(2k?1),则22n?10?(k?1)?(k?2).由于k?1和k?2是一奇一偶，左边

11

n?10?22知n?12为所求. 为2的幂，因而只能k?1=1，于是得k?2，由2

12

本文来源：https://www.bwwdw.com/article/z8c3.html