初中数学竞赛讲座——数论部分2(整数的整除性)

2023年6月13日发(作者：)

-

初中数学兴趣班系列讲座——数论部分 唐一良数学工作室

第二讲 整数的整除性

一、基础知识：

1．整除的基本概念与性质

所谓整除，就是一个整数被另一个整数除尽，其数学定义如下．

定义： 设a，b是整数，b≠0．如果有一个整数q，使得a=bq，那么称a能被b整除，或称b整除a，并记作b｜a．也称b是a的约数，a是b的倍数。

如果不存在这样的整数q，使得a=bq，则称a不能被b整除，或称b不整除a，记作b｜a．

关于整数的整除，有如下一些基本性质：

性质1若a|b,b|c，则a|c

证明：∵a|b,b|c，∴bap,cbq（p,q是整数），

∴c(ap)q(pq)a，∴a|c

性质2 若a｜b，b｜a，则 |a|=|b|．

性质3 若c｜a，c｜b，则c｜(a±b)，且对任意整数m，n，有c｜(ma±nb)．

证明：∵a|b,a|c，∴bap,caq(b,q是整数），

∴bcapaqa(pq)，∴a|(bc)

性质4 若b｜a，d｜c，则bd｜ac．特别地，对于任意的非零整数m，有bm｜am

性质5 若a=b＋c，且m｜a，m｜b，则m｜c．

性质6 若b｜a，c｜a，则[b，c]｜a．特别地，当(b，c)=1时，bc｜a

【此处[b，c]为b，c的最小公倍数；(b，c)为b，c的最大公约数】．

性质7 若c｜ab，且(c，a)=1，则c｜b．特别地，若p是质数，且p｜ab，则p｜a或p｜b．

性质8 n个连续整数中，必有一个能被n整除．

【特别地：两个连续整数必有一偶数；三个连续整数必有一个被3整除，如11，12，13中有3 | 12；41，42，43，44中有4 |44；77，78，79，80，81中5 | 80．】

二．证明整除的基本方法

证明整除常用下列几种方法：(1)利用基本性质法；(2)分解因式法；(3)按模分类法；(4)反证法等．下面举例说明．

例1若a｜n，b｜n，且存在整数x，y，使得ax+by=1，证明：ab|n． 初中数学兴趣班系列讲座——数论部分 唐一良数学工作室

证明：由条件，可设n=au ， n=bv，u，v为整数，于是

n=n(ax+by)= nax+nby=abvx+abuy= ab(vx+uy)

所以n|ab

例2 证明：三个连续奇数的平方和加1，能被12整除，但不能被24整除．

分析 要证明一个数能被12整除但不能被24整除，只需证明此数等于12乘上一个奇数即可．

证明：设三个连续的奇数分别为2n-1，2n＋1，2n+3(其中n是整数)，于是

(2n-1)2+(2n+1)2+(2n+3)2＋1=12(n2＋n＋1)．

所以12｜[(2n-1)2＋(2n＋1)2＋(2n＋3)2]．

又n2+n＋1=n(n＋1)+1，而n，n+1是相邻的两个整数，必定一奇一偶，所以n(n+1)是偶数，从而n2＋n+1是奇数，故

24

|[(2n-1)2+(2n+1)2＋(2n＋3)2]．

例3 若整数a不被2和3整除，求证：24｜(a2-1)．

分析 因为a既不能被2整除，也不能被3整除，所以，按模2分类与按模3分类都是不合适的．较好的想法是按模6分类，把整数分成6k，6k＋1，6k＋2，6k＋3，6k＋4，6k＋5这六类．由于6k，6k＋2，6k＋4是2的倍数，6k＋3是3的倍数，所以a只能具有6k＋1或6k＋5的形式，有时候为了方便起见，也常把6k＋5写成6k-1(它们除以6余数均为5)．

证明 因为a不被2和3整除，故a具有6k±1的形式，其中k是自然数，所以a2-1=(6k±1)2-1=36k2±12k=12k(3k±1)．由于k与3k±1为一奇一偶(若k为奇数，则3k±1为偶数，若k为偶数，则3k±1为奇数)，所以2｜k(3k±1)，于是便有24｜(a2-1)．

例4 若x，y为整数，且2x+3y，9x＋5y之一能被17整除，那么另一个也能被17整除．

证明： 设u=2x＋3y，v=9x＋5y．若17｜u，从上面两式中消去y，得

3v-5u=17x．①

所以 17｜3v．

因为(17，3)=1，所以17｜v，即17｜9x＋5y．

若17｜v，同样从①式可知17｜5u．因为(17，5)=1，所以17｜u，即17｜2x＋3y．

例5 已知a，b是自然数，13a＋8b能被7整除，求证：9a+5b都能被7整除．

分析：考虑13a＋8b的若干倍与9a+5b的若干倍的和能被7整除，

证明 13a＋8b+4（9a+5b）=7（7a+4b）是7的倍数，又已知13a+8b是7的倍数，所以4（9a+5b）是7的倍数，

因为4与7互质，由性质7|（9a+5b）

例6 已知a，b是整数，a2＋b2能被3整除，求证：a和b都能被3整除． 初中数学兴趣班系列讲座——数论部分 唐一良数学工作室

证明 用反证法．如果a，b不都能被3整除，那么有如下两种情况：

(1) a，b两数中恰有一个能被3整除，不妨设3｜a，3b．令a=3m，b=3n±1(m，n都是整数)，于是

a2+b2=9m2+9n2±6n+1

=3(3m2＋3n2±2n)+1，

不是3的倍数，矛盾．

(2) a，b两数都不能被3整除．令a=3m±1，b=3n±1，则

a2＋b2=(3m±1)2+(3n±1)2

=9m2±6m+1+9n2±6n＋1

=3(3m2+3n2±2m±2n)＋2，

不能被3整除，矛盾．

由此可知，a，b都是3的倍数．

例7 已知a，b是正整数，并且a2＋b2能被ab整除，求证：a=b．

先考虑a，b互质的情况，再考虑一般情况。

证明 (1)若a，b互质，那么由ab|a2＋b2，得a|a2＋b2，从而a|b2，又a，b互质，得a=1

同理b=1，所以a=b；

(2) 若a，b不互质，则设d为它们的最大公约数，

a=a1d ， b=b1d，则a1，b1互质，

由ab|a2＋b2，得a1b1d2| d2(a12＋b12)，

从而a1b1| (a12＋b12)，

由（1）可知a1=b1=1

所以a=b=d

例8 设p是质数，证明：满足a2=pb2的正整数a，b不存在．

证明 用反证法．假定存在正整数a，b，使得

a2=pb2

令(a，b)=d，a=a1d，b=b1d，则(a1，b1)=1．所以

a12d2=pb12d2，a12=pb12

所以p|a1，由于p是质数，所以p|a1，令a1pa2，则a1pa2，则pa2b1

222初中数学兴趣班系列讲座——数论部分 唐一良数学工作室

同理p|b1，即a1，b1都有p这个因子，与(a1，b1)=1矛盾．

例9 若p，q，解 若p=q，则

2p12q1，都是整数，并且p＞1．求pq的值．

qp2p12p112

qpp不是整数，所以p≠q．不妨设p＜q，于是

1而2p12q12q2

qqq2p12p1是整数，故=1，即q=2p-1，

qq2q14p33又4是整数，所以p只能为3，从而q=5．

ppp所以pq=3×5=15．

例10 试求出两两互质的不同的三个自然数x，y，z，使得其中任意两个的和能被第三个数整除．

分析 题中有三个未知数，我们设法得到一些方程，然后从中解出这些未知数．

解 不妨设xyz，于是yzxzxy，，都是自然数，先考虑最小的一个：

yxz1xyzz2

zz所以xzx+y，因为y|(xz)，即

1，即zxy，再考虑yz2x2y2

yy

y｜(y＋2x)，所以y｜2x，于是1所以2x1，即y2x，从而这三个数为x,2x,3x，又因为这三个数两两互质，所以x=1．

y 所求的三个数为1，2，3．

例11 设n是奇数，求证：

60｜6n-3n-2n-1．

分析 因为60=22×3×5，22，3，5是两两互质的，所以由性质6，只需证明22，3，5能被6n-3n-2n-1整除即可．对于幂的形式，我们常常利用性质8～性质10，其本质是因式分解．

证明 60=22×3×5．由于n是奇数，利用性质8和性质10，有

22｜6n-2n，22｜3n＋1， 初中数学兴趣班系列讲座——数论部分 唐一良数学工作室

所以

22｜6n-2n-3n-1， 3｜6n-3n， 3｜2n+1，

所以

3｜6n-3n-2n-1，5｜6n-1，5｜3n+2n，

所以

5｜6n-1-3n-2n．

由于22，3，5两两互质，所以

60｜6n-3n-2n-1．

【注】我们通常把整数分成奇数和偶数两类，即被2除余数为0的是偶数，余数为1的是奇数．偶数常用2k表示，奇数常用2k+1表示，其实这就是按模2分类．又如，一个整数a被3除时，余数只能是0，1，2这三种可能，因此，全体整数可以分为3k，3k＋1，3k＋2这三类形式，这是按模3分类．有时为了解题方便，还常把整数按模4、模5、模6、模8等分类，但这要具体问题具体处理．

例12 求证：3n+1(n为正整数)能被2或22整除，但不能被2的更高次幂整除．

证明 按模2分类．若n=2k为偶数，k为正整数，则

3n＋1=32k＋1=(3k)2＋1．

由3k是奇数，(3k)2是奇数的平方，奇数的平方除以8余1，故可设(3k)2=8l＋1，于是

3n＋1=8l＋2=2(4l＋1)．

4l＋1是奇数，不含有2的因数，所以3n＋1能被2整除，但不能被2的更高次幂整除．

若n=2k＋1为奇数，k为非负整数，则

3n+1=32k1+1=3·(3k)2＋1

＋ =3(8l＋1)＋1=4(6l＋1)．

由于6l＋1是奇数，所以此时3n+1能被22整除，但不能被2的更高次幂整除．

在解决有些整除性问题时，直接证明较为困难，可以用反证法来证．

例13 设m是一个大于2的正整数，证明：对任意正整数n，都有21|21

mn证明：如果存在正整数n，使得21|21，那么取其中最小的那个n，

mn由于m>2，知n>1，进一步，应有2121，知nm

mnnmn而n=m时，21|2（因为2(21)(21)，右边每一项都是2n-1的倍数），矛盾，故n>m 初中数学兴趣班系列讲座——数论部分 唐一良数学工作室

于是设21(21)q，这里q是正整数，则

nm2n2m(2n1)(2m1)(2m1)(q1)

即

2(2mnm1)(2m1)(q1)

于是

(2nm1)(2m1)(2nm1)(2m1)(q1)

nm得

(21)(2m1)(q2nm)

因此，21|2mnm+1，与n的最小性矛盾，

所以，命题成立。

例14 设p，q均为自然数，且

p1111111

q23451819求证：29｜p．

证明 注意到29是质数．令a=10×11×…×19．

所以 ap=29q·b，

初中数学兴趣班系列讲座——数论部分 唐一良数学工作室

29｜a·p，29是质数，且29a，所以29｜p．

例15. 用正方形的地砖不重叠、无缝隙地铺满一块地，选用边长为x（cm）规格的地砖，恰用n块；若选用边长为y（cm）规格的地砖，则要比前一种刚好多用124块．已知x、y、n都是正整数，且（x，y）=1．试问：这块地有多少平方米？

解：设这块地的面积为S，则S=nx2=（n+124）y2，得n（x2-y2）=124y2．

∵x＞y，（x，y）=1，

∴（x2-y2，y2）=l，得（x2-y2）|124．

∵124=22×31，x2-y2=（x十y）（x-y），x十y＞x-y，且x十y与x-y奇偶性相同，

xy31xy312或

xy1xy2解之得x=16，y=15，此时n=900．故这块地的面积为S=nx2=900×162=230400（cm2）=23.04（m2）．

故答案为：23.04m2．

例16 已知1996个自然数a1，a2，…a1996两数的和能被它们的差整除，现设n=a1•a2•a3•…•a1996．

求证：n，n+a1，n+a2，…，n+a1996这1997个数仍满足上述条件．

证明：由于自然数是有序的，因此我可以把他们排列从小到大，不妨设a1＜a2＜a3…＜a1996，

① 证明a1，a2…a1996任取3个，一定有一个是偶数．假设任取三个ai，aj，ak，它们全部都是奇数，那么他们可以表示成ai=a，aj=a+2b，ak=a+2c，其中a，b，c为正整数，且a为奇数，b＜c，我这样做因为他们肯定相隔偶数．由已知aj-ai|ai+aj，ak-ai|ai+ak，ak-aj|aj+ak，

得到b|a+b，即b|a，c|a+c，即c|a，故c-b|a+b+c，

因此b，c都是奇数，那么a+b+c是3个奇数相加，因此也是奇数，然而c-b是两个奇数相减，因此是偶数，那么不可能一个偶数c-b能除尽奇数a+b+c，因此得到矛盾，所以不可能都是奇数．

②从a1，…a1996任取两个ai，aj，其中ai＜aj，下面证明aj-ai|n．

由aj-ai|ai+aj，可得aj-ai|（ai+aj）2=ai2+2aiaj+aj2=（aj-ai）2+4aiaj

由于aj-ai|（aj-ai）2所以aj-ai|4aiaj

在①里面，可见任何3个数中，必有一个是奇数，因此a1，a2，…a1996至少有2个偶数不等于ai，aj，

因此，显然4aiaj|n，所以aj-ai|n

③从n，n+a1，n+a2，…n+a1996任取两个n+ai，n+aj，其中ai＜aj

他们两个之差=aj-ai

之和=2n+ai+aj因为aj-ai|n（②中证明的） 和 aj-ai|ai+aj（已知条件）

所以aj-ai|2n+ai+aj，这样证明了任取两个数属于{n，n+a1，n+a2…n+a1996}，他们之和能被他们之差整除．

例17．从1，2，…，9中任取n个数，其中一定可以找到若干个数(至少一个，也可以是全部)，它们的和能被10整除，求n的最小值．

当n＝4时，数1，3，5，8中没有若干个数的和能被10整除． 初中数学兴趣班系列讲座——数论部分 唐一良数学工作室

当n＝5时，设a1，a2，，a5是1，2，…，9中的5个不同的数．若其中任意若干个数，它们的和都不能被10整除，则a1，a2，，a5中不可能同时出现1和9；2和8；3和7；4和6．于是a1，a2，，a5中必定有一个数是5．

，a5中含1，则不含9．于是不含4（4＋1＋5＝10）若a1，a2，，故含6；于是不含3（3＋6＋1＝10），故含7；于是不含2（2＋1＋7＝10），故含8．但是5＋7＋8＝20是10的倍数，矛盾．

，a5中含9，则不含1．于是不含6（6＋9＋5＝20）若a1，a2，，故含4；于是不含7（7＋4＋9＝20），故含3；于是不含8（8＋9＋3＝10），故含2．但是5＋3＋2＝10是10的倍数，矛盾．

综上所述，n的最小值为5.

三、模拟训练

1．已知九位数32a35717b能被72整除，求a,b．

解：∵7232a35717b，而7289，∴8 |

32a35717b，9 |

32a35717b．

根据数的整除特征，有8|17b，且b必须是偶数，

∴b6，又9|(32a357176)，

即9|(34a)，∴a2

2．已知N13xy45z能被792整除，试确定数字x,y,z及N．

解：∵7928911，∴8|N，∴8|45z，∴z6，

又9|N，∴9|(13xy456)，即9|(19xy)

∴xy18，或xy17，又11|N，∴11|[(1x46)(3y5)]，

即11|[3(xy)]，∴xy8，或xy3

xy8,x8,经检验，符合题意，它的解是故N1380456．

xy8,y0,3．用0，1，2，3，…，9这十个不同的数字组成能被99整除的十位数，求其中最大的一个数和最小的一个数．

分析：因为99=9×11，所以这个十位数能同时被9和11整除．

解：∵0+1+2+…+9=45=5×9，∴所有这样的十位数均能被9整除，

设十位数中奇数位上数字和为x，偶数位上数字和为y，则xy012+…+9= 45为奇数，

xy为奇数．

根据题意，得11|(xy)，∴|xy|11， 初中数学兴趣班系列讲座——数论部分 唐一良数学工作室

若xy11，则x28,y17；若xy11，则x17,y28

要使十位数最大，前几位应尽量选用9，8，7，6；

若前四位为9876，则9+7=16，8+6=14，可知x17，于是有x28,y17．

从而易得能被99整除的最大的十位数为9876524130

同理能被99整除的最小的十位数为1024375869．

说明：注意到xy与xy奇偶性相同，在得|xy|0，11，22时就可以排除

|xy|0与|xy|22．

4．从19到80的所有两位数被连续地写成一个数x19202122…7980，求证：这个数能被1980整除．

分析：显然20|x，由1980=20×9×11，故1980 |x，这个数能被1980整除．

想一想

证明11 | x时，也可证19+20+21+…+79+80= 99×31能被11整数整除，这是为什么？

5．若4b2cd32，试问abcd能否被8整除？请说明理由．

分析：要说明abcd能否被8整除，根据被8整除的数的特征，只要判断bcd能否被8整除．

解：bcd100b10cd96b8c(4b2cd)96b8c32

8(12bc4)，∴8|bcd，∴8|abcd

6．若a,b,c,d是互不相等的整数，且整数x满足等式(xa)(xb)(xc)(xd)9

求证：4|(abcd)

证明：∵a,b,c,d是互不相等的整数，∴xa,xb,xc,xd也是互不相等的整数．∵(xa)(xb)(xc)(xd)9，∴xa,xb,xc,xd均为9的约数，

而9(1)(1)(3)(3)，∴(xa)(xb)(xc)(xd)

(1)(1)(3)(3)0，即abcd4x，故4|(abcd)．

7．求证：10001 能被11整除．

8个0证明：10001101(10)1(101)(10101)

8个0933363=(101)(10101)(10101)11(10101)(10101)

∴10001 能被11整除．

8个02632638．已知x,y,z均为整数，若11|(7x2y5z)，求证：11|(3x7y12z)． 初中数学兴趣班系列讲座——数论部分 唐一良数学工作室

证明：∵4(3x7y12z)3(7x2y5z)11(3x2y3z)

又∵11|(7x2y5z)，11|11(3x2y3z)

∴11|4(3x—7y12z)，又∵11，4互质，∴11|(3x7y12z)

9．试证：n为整数时，n(n1)(2n1)是6的倍数．

证明：∵n(n1)(2n1)n(n1)[(n2)(n1)]

n(n1)(n2)(n1)n(n1)，又n,n1,n2是三个连续整数，

∴n(n1)(2n1)是123的倍数，即6|n(n1)(n2)；

同理6|(n1)n(n1)，∴6|[n(n1)(n2)(n1)n(n1)]，即6|n(n1)(2n1)

10．一整数a若不能被2和3整除，则a47必能被24整除．

证明：因为a47(a1)48，且48能被24整除，故只需证a1能被24整除，a47就能被24整除

∵a不能被2整除，∴a为奇数，设a2k1(k是整数），

则a1(2k1)14k(k1)能被8整除

∵a(a1)(a1)a(a1)能被3整除，而a不能被3整除

∴a1能被3整除，又3与8互质，故a1能被24整除

11．已知a,b为整数，且9|(aabb)，求证：3|a，3|b．

分析：由aabb(ab)3ab，得3|(ab)，从而3|(ab)

证明：∵aabb(ab)3ab，9|(aabb)

∴3|[(ab)3ab]，∴3|(ab)，∵3是质数，∴3|(ab)

又∵9|[(ab)3ab]，∴9|3ab，∴3|ab，∵3是质数，∴3|a,或3|b

若3|a，由3|(ab)，得3|b，若3|b，同理可得3|a．故3|a,3|b．

说明：3|ab是显然的，但它不能保证3|a与3|b同时成立．

12 .一个整数称为可被其数字和整除．如果：

（1） 它的数字都不为0；

（2）它可以被它的数字和整除（例如322可被其数字和整除）．

222222222222222222222222初中数学兴趣班系列讲座——数论部分 唐一良数学工作室

证明：有无限多个可被数字和整除的整数．

证明：322可被其数字和整除，即322÷7=46

322×10÷7=46×10=460

322×102÷7=46×102=4.6×103；

依此类推：322×10n÷7=46×10n=4.6×10n+1

n是任意的整数，因而322×10n即3.22×10n+2都是可被数字和整除的整数．

故有无限多个可被数字和整除的整数．

13.某商场向顾客发放9999张购物券，每张购物券上印有一个四位数的号码，从0001到9999号，如果号码的前两位数字之和等于后两位数字之和，则称这张购物券为“幸运券”．证明：这个商场所发放的购物券中，所有的幸运券的号码之和能被101整除．

解：“如果某个号码n是幸运券，那么号m=9999-n也是幸运券”，这是解决问题的关键，请你考虑这句话合理性．

若六位数81ab93是99的倍数，求整数a、b的值．

∵81ab93能被9整除，

∴8+1+a+b+9+3=21+a+b能被9整除，得3+a+b=9kl（k1为整数）．①

又∵81ab93能被11整除，

∴8-1+a-b+9-3=13+a-b能被11整除，得2+a-b=11k2（k2为整数）．②

∵0≤a，b≤9，

∴0≤a+b≤18，-9≤a-b≤9，

由①、②两式，得3≤＜9k1≤21，-7≤11k2≤11，

知k1=1，或k1=2；k2=0，或，而3+a+b与2+a-b的奇偶性相异，而k1=2，k2=1不符合题意．

故把k1=1，k2=0代入①、②两式，解方程组可求得a=2，b=4．代入所设6位数．即得到812493．

所以，这个商场所发放的购物券中，所有的幸运券的号码之和能被101整除．

14.试找出由0，1，2，3，4，5，6这7个数字组成的没有重复数字的七位数中，能被165整除的最大数和最小数（要求写出推理过程）．

解：∵165=3×5×11

∴此7位数必同时能被3，5，11整除，而0+1+2+3+4+5+6=21能被3整除，

∴排成的7位数只需能同时被11，5整除即可，

根据能被11整除的数的性质，设7位数奇位上的数字和为x，偶数位上的数字和为y，则

x-y是11的倍数而x-y与x+y的奇偶性相同，且x+y=21，

∴只有x-y=11或-11，即x=5，y=16或x=16，y=5

∵7位数能被5整除，

∴其末位数必为0或5，

当末位数必为0或5时，找不到4个数的和为5，

∴只有x=16，y=5，即该7位数的奇数位上的数字和为16，偶数位上的数字和为5，且其末位数必为5．

只有两组分法：

①、奇数位上的数字（1，4，6，5），偶数位上的数字（0，2，3）

②、奇数位上的数字（2，3，5，6）偶数位上的数字（0，1，4）

①中最大数和最小数分别为6342105和1042635；②中最大数和最小数分别为6431205和2031645

∴所求的最大数和最小数分别为6431205和1042635．

故答案为：6431205和1042635．

-