初中数学竞赛讲座

本文格式为Word版，下载可任意编辑——初中数学竞赛讲座初中数学兴趣班系列讲座——数论部分唐一良数学工作室

其次讲整数的整除性

一、基础知识：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

．

性质7若c｜ab，且(c，a)=1，则c｜b．特别地，若p是质数，且p｜ab，则p｜a或p｜b．性质8n个连续整数中，必有一个能被n整除．

二．证明整除的基本方法

证明整除常用以下几种方法：(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=ab+abuy=ab(+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???2q2p?12p?1是整数，故=1，即q=2p-1，2q?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??2zz所以

x?zx+y，由于y|(x?z)，即?1，即z?x?y，再考虑yz2x2y??2yyy｜(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的更高次幂整除．在解决有些整除性问题时，直