金湖县实验中学高中数学奥赛辅导数论初步—数的整除性

奥数数的整除讲义、练习含答案（推荐文档）数的整除（1）性质、特征、奇偶性知识要点】：整除性质：（1）如果数a、b都能被c整除，那么它们的和（a+b）或差（a—b）也能被c整除。

2）如果数a 能被自然数b 整除，自然数b 能被自然数c 整除，则数a 必能被数c 整除。

3）若干个数相乘，如其中有一个因数能被某一个数整除，那么，它们的积也能被这个数整除。

4）如果一个数能被两个互质数中的每一个数整除，那么，这个数能被这两个互质数的积整除。

反之，若一个数能被两个互质数的积整除，那么这个数能分别被这两个互质数整除。

整除特征：（1）若一个数的末两位数能被4（或25）整除，则这个数能被4（或25）整除。

2）若一个数的末三位数能被8（或125）整除，则这个数能被8（或125）整除。

3）若一个数的各位数字之和能被3（或9）整除，则这个数能被3或9）整除。

4）若一个数的奇数位数字和与偶数数字和之差（以大减小）能被11 整除，则这个数能被11 整除。

5）若一个数的末三位数字所表示的数与末三位以前的数字所表示的数之差（大数减小数）能被7（或13）整除，则这个数能被7（或13）整除。

奇数±奇数 =偶数（ 2）偶数±偶数 =偶数（ 3）奇数±偶奇数X 奇数二奇数（5）偶数X 偶数二偶数（6）奇数X 偶典型例题】例 1：一个三位数能被 3 整除，去掉它的末尾数后，所得的两位数是17 的倍数，这样的三位数中，最大是几？例2: 1?200这200个自然数中，能被6或8整除的数共有多少个?奇偶性：（1）数 =奇数（ 4）数=偶数（ 7）奇数一奇数二奇数（8）…例3 ：任意取出1998 个连续自然数，它们的总和是奇数还是偶数？例4：有“ 1”，“ 2 ”，“ 3 ”4”四张卡片，每次取出三张组成三位数，其中偶数有多少个？例5如杲41位数5亍-5口99…9能被7整除，那么中间方格内的数字是几? 【精英班】PT'【竞赛班】例6：某市举办小学生数学竞赛，共20道题，评分标准是: 答对一题给5分，不答一题给1分，答错一题倒扣1分，如果1999人参赛，问参赛同学的总分是奇数还是偶数?【课后分层练习】A组：入门级1、判断306371 能否被7整除？能否被13整除?2、abcabc能否被7、11和13整除？3、六位数7E36F5 是1375的倍数，求这个六位数。

数论初步整数的性质与应用整数是数论中的基本概念之一，它在数学和实际应用中扮演着重要角色。

本文将介绍数论初步中整数的性质和应用。

一、整数的定义及性质整数是由正整数、负整数和零组成的集合。

它们具有以下性质：1. 加法性质：对于任意两个整数a和b，它们的和a+b也是一个整数。

2. 减法性质：对于任意两个整数a和b，它们的差a-b也是一个整数。

3. 乘法性质：对于任意两个整数a和b，它们的积ab也是一个整数。

4. 整数的封闭性：整数集合在加法和乘法运算下都是封闭的，即对于任意两个整数a和b，它们的和a+b和积ab仍然是整数。

二、整数的因数和倍数1. 因数：对于整数a和b，如果存在整数c使得a=bc，那么称b是a的因数，a是b的倍数。

特别地，一个数的因数中必然包含1和它本身。

2. 素数和合数：如果一个大于1的整数只有1和它本身两个因数，那么它被称为素数；否则，它被称为合数。

素数是整数中最基本的构成单元，每一个合数都可以分解为若干个素数的乘积。

三、整数的整除、互质和最大公因数1. 整除和余数：对于整数a和b，如果存在整数c，使得a=bc，那么称a能被b整除，b能整除a，记作b|a。

如果a不能被b整除，那么称a不能被b整除，记作b∤a。

除法算式中的余数指的是满足整数除法关系的余数。

2. 互质：如果两个整数a和b的最大公因数是1，那么称a和b是互质的。

3. 最大公因数：a和b的最大公因数是同时能整除a和b的最大整数，记作gcd(a, b)。

最大公因数可以用辗转相除法求得。

四、整数的质因数分解1. 质因数：一个大于1的整数的质因数是指能整除它的素数因子。

每一个整数都可以唯一地分解成多个质因数的乘积。

2. 质因数分解：将一个合数分解为质因数的乘积的过程被称为质因数分解。

五、整数的应用1. 模运算：模是整数除法中的余数。

模运算在密码学等领域有着重要应用。

2. 同余定理：同余是指两个整数除以同一个正整数所得的余数相等。

第二十四讲* 整数的整除性整数的整除性问题，是数论中的最基本问题，也是国内外数学竞赛中最常出现的内容之一．由于整数性质的论证是具体、严格、富有技巧，它既容易使学生接受，又是培养学生逻辑思维和推理能力的一个有效课题，因此，了解一些整数的性质和整除性问题的解法是很有必要的．1．整除的基本概念与性质所谓整除，就是一个整数被另一个整数除尽，其数学定义如下．定义设a，b是整数，b≠0．如果有一个整数q，使得a=bq，那么称a能被b整除，或称b整除a，并记作b｜a．如果不存在这样的整数q，使得a=bq，则称a不能被b整除，或称b不整除a，记作ba．关于整数的整除，有如下一些基本性质：性质1 若b｜a，c｜b，则c｜a．性质2 若c｜a，c｜b，则c｜(a±b)．性质3 若c｜a，cb，则c(a±b)．性质4 若b｜a，d｜c，则bd｜ac．性质5 若a=b＋c，且m｜a，m｜b，则m｜c．性质6 若b｜a，c｜a，则[b，c]｜a(此处[b，c]为b，c的最小公倍数)．特别地，当(b，c)=1时，bc｜a(此处(b，c)为b，c的最大公约数)．性质7 若c｜ab，且(c，a)=1，则c｜b．特别地，若p是质数，且p｜ab，则p｜a或p｜b．性质8 若a≠b，n是自然数，则(a-b)｜(an-bn)．性质9 若a≠-b，n是正偶数，则(a＋b)｜(an-bn)．性质10 若a≠-b，n是正奇数，则(a＋b)｜(an＋bn)．2．证明整除的基本方法证明整除常用下列几种方法：(1)利用基本性质法；(2)分解因式法；(3)按模分类法；(4)反证法．下面举例说明．例1 证明：三个连续奇数的平方和加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]．例2 若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．q＞1．求pq的值．解若p=q，则不是整数，所以p≠q．不妨设p＜q，于是是整数，所以p只能为3，从而q=5．所以pq=3×5=15．例4 试求出两两互质的不同的三个自然数x，y，z，使得其中任意两个的和能被第三个数整除．分析题中有三个未知数，我们设法得到一些方程，然后从中解出这些未知数．最小的一个：y｜(y＋2x)，所以y｜2x，于是数两两互质，所以x=1．所求的三个数为1，2，3．例5 设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等分类，但这要具体问题具体处理．例6 若整数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)．例7 求证：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=32k＋1+1=3·(3k)2＋1=3(8l＋1)＋1=4(6l＋1)．由于6l＋1是奇数，所以此时3n+1能被22整除，但不能被2的更高次幂整除．在解决有些整除性问题时，直接证明较为困难，可以用反证法来证．例8 已知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的倍数．例9 设p是质数，证明：满足a2=pb2的正整数a，b不存在．证用反证法．假定存在正整数a，b，使得a2=pb2令(a，b)=d，a=a1d，b=b1d，则(a1，b1)=1．所以与(a1，b1)=1矛盾．例10 设p，q均为自然数，且求证：29｜p．证注意到29是质数．令a=10×11× (19)所以ap=29q·b，29｜a·p，29是质数，且29a，所以29｜p．练习二十四1．求证：对任意自然数n，2×7n＋1能被3整除．2．证明：当a是奇数时，a(a2-1)能被24整除．3．已知整数x，y，使得7｜(13x+8y)，求证：7｜(9x＋5y)．4．设p是大于3的质数，求证：24｜(p2-1)．5．求证：对任意自然数n，n(n-1)(2n-1)能被6整除．6．求证：三个连续自然数的立方和能被9整除．7．已知a，b，c，d为整数，ab＋cd能被a-c整除，求证：ad＋bc也能被a-c整除．。

数的整除知识点总结数的整除是数论中的一个基本概念，也是初等数学中的重要内容。

它与因数、倍数和约数等概念密切相关，对于解题和推理都有着重要的作用。

下面将对数的整除进行详细总结。

一、定义：如果整数a能够被整数b整除，即a/b是整数，那么称a是b的倍数，b是a的因数。

可以用数学表达式a=b*k来表示，其中k是整数。

二、性质：1.任何一个整数都是它自身的倍数，也是它自身的因数，即a是a的倍数，a是a的因数。

2.任何一个正整数都是1的倍数，即对于任何整数a，都有a是1的倍数。

3.任何一个整数都是它自身的因数，即对于任何整数a，都有a是a的因数。

4.如果a是b的倍数，b是c的倍数，那么a也是c的倍数，即若a是b的倍数且b是c的倍数，则a是c的倍数。

5.如果a是b的倍数，b是a的倍数，那么a和b是互为倍数，即a是b的倍数且b是a的倍数，则a和b互为倍数。

6.如果a是b的因数，b是c的因数，那么a也是c的因数，即若a是b的因数且b是c的因数，则a是c的因数。

三、判断一个数能否整除另一个数的方法：1.因式分解法：将被除数和除数都分解成质因数的乘积形式，然后进行比较。

如果被除数的质因数包含除数的质因数，并且对应质因数的指数均大于等于相应的质因数的指数，则被除数能够整除除数。

2.试商法：用除数去除被除数，如果商是整数且余数为0，则被除数能够整除除数，否则不能整除。

四、整除的性质：1.整除关系具有传递性，即如果a能够整除b，b能够整除c，则a 能够整除c。

2.整除关系具有反对称性，即如果a能够整除b，b能够整除a，则a 和b相等或互为相反数。

3.整除关系具有自反性，即任何一个数都能整除它本身。

4.整除关系具有非传递性，即如果a能够整除b，b能够整除c，但a 不能整除c。

例如：2能整除4，4能整除8，但2不能整除8五、整数的混合运算与整除的关系：1.若a整除b，b整除c，则a整除c。

2. 若a整除b，b整除c，则a整除bc。

数的整除性质数的整除性质是数学中一个非常基础且重要的概念。

整除是指一个数能够被另一个数整除，即能够整除的数叫做除数，能够被整除的数叫做被除数。

在数的整除性质中，有一些基本的定理和规律，我们一起来探讨。

一、整除的定义在数学中，如果存在整数a和b，使得b乘以a得到的结果等于一个整数c，那么我们就说b能够整除c。

这个定义可以用符号表示为：b|c，读作“b整除c”。

例如，4能够整除12，我们可以表示为4|12。

二、整除的性质1. 传递性：如果a能够整除b，b能够整除c，那么a一定能够整除c。

例如，如果2能够整除4，4能够整除8，那么2一定能够整除8。

2. 自身整除：任何一个数都能够整除自身。

例如，5能够整除5。

3. 1整除任何数：1能够整除任何一个数。

例如，1能够整除8。

4. 零的整除性：任何一个数都能够整除0。

例如，任何数都能够整除0。

5. 任何一个数都能够整除1：任何一个数都能够被1整除。

例如，任何数都能够被1整除。

6. 如果a能够整除b，那么a能够整除b的倍数。

例如，如果3能够整除6，那么3一定能够整除6的倍数12。

7. 如果a能够整除b，那么b能够整除a的因数。

例如，如果2能够整除4，那么4一定能够整除2的因数。

三、整除和最大公因数最大公因数是指两个或多个整数中最大的能够整除这些整数的数。

最大公因数可以通过求解数的因数来得到。

例如，求解12和15的最大公因数，我们可以找到12的因数：1、2、3、4、6、12，15的因数：1、3、5、15，他们的公因数有1和3，其中最大的公因数是3。

最大公因数有以下的性质：1. 最大公因数是两个数的公因数中最大的一个。

2. 如果最大公因数为1，那么这两个数互质。

3. 如果最大公因数为a，那么这两个数的倍数中最大的一个为a。

四、整除与质数质数是指大于1的正整数，除了1和本身，没有其他的因数。

质数和整除有着密切的关系。

1. 质数只能被1和自身整除。

2. 任何一个数都可以被质数整除。

数学奥赛辅导第二讲整除数学奥赛辅导第二讲整除数学奥赛辅导第二讲相乘知识、方法、技能相乘就是整数的一个关键内容，这里仅了解其中的几个方面：整数的相乘性、最大公约数、最轻公倍数、方幂问题.ⅰ.整数的整除性初等数论的基本研究对象就是自然数子集及整数子集.我们晓得，整数子集中可以作加、减至、乘法运算，并且这些运算满足用户一些规律（即为乘法和乘法的结合律和交换律，乘法与乘法的分配律），但通常无法搞乘法，即为，如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?a2an,则p必能整除a1,a2,?,an中的某一个.特别地，若p为质数，p|an,则p|a.（7）例如在等式abii1k1nmk中除开某一项外，其余各项都是c的倍数，则这一项也是c的倍数.（8）n个已连续整数中有且只有一个就是n的倍数.（9）任何n个已连续整数之内积一定就是n的倍数.本讲开始在整除的定义同时给出了约数的概念，又由上一讲的算术基本定理，我们就可以讨论整数的约数的个数了.定理一：设立大于1的整数a的标准水解式为a?p11?p2?pnn(p1?p2pn为质数，?i 均为非负整数），则a的约数的个数为d(a)??（?i?1).i?1n所有的约数和为：(a)i1npii11.pi?1事实上，由算术基本定理的推断言d(a)??(?i?1ni?1)，而各约数的和就是(1pi1nipaii)展开后的各项之和，所以nn?ip1?1?(a)??(1?pipi)??i?1i?1pi?1?i比如，25200=2432527，所以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?则pi1nii，,b??pi?i(pi为质数，ai,?i为非负整数）i?1n(a,b)??pimin(?i,?i)①i?1nn[a,b]??piman(?i,?i)②i?1比如3960=2332511，756=22337，则（3960，756）=2232=36，[3960，756]=23335711=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?r1rn?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）3780720180（r1）36（r2）5（q3）1800（r3）由定义和上述求法不难得出最大公约数和最小公倍数的如下性质：（1）m?n,则(am,bm)?m(a,b).（2）设c为a,b的公约数，则(,)?abcc(a,b)ab.特别地，若c?(a,b),则(,)?c（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]?pi1nimin(i,i)piiiab.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。

第四讲初等数论1——整除性本讲概述数论是数学中极其重要又非常迷人的一个分支，目前我们仅学习初等数论中较浅的内容.初等数论是数学竞赛四大模块中较难以掌握的模块之一，在数学竞赛中占据极其重要的位置.特别是联赛改制以后，二试必考一道50分的数论大题，一试也会有一到两道数论方面的问题.数论与组合水平如何是大家能否获得联赛一等奖甚至更好成绩的关键.初等数论这块的竞赛问题涉及到的知识点极少，甚至可以说绝大部分同学在小学初中的培训中基本都接触过.但是限于初中的知识面和同学的年龄，考试中一般不出现较为深入、难度较高的数论问题.到了高中，大家将复习小学初中阶段的数论知识，并将其中的很多知识更为理论化、系统化.高中的数论问题难度也会明显增高. 但是在数论这一模块中，我们并不提倡大家过多地掌握很多高深的数论知识，而是提倡大家真正去灵活熟练地运用最基本、最重要的数论基础知识和重要定理来解决问题.由于同学们在小学、初中都已经学过不少关于初等数论的初步知识，所以这里我们把大家比较熟悉的知识都罗列在下面，对其中大部分定理将不给出证明，直接给出结论.如果不特别说明，本讲中所有字母均代表正整数.一、整除1．整除的定义两个整数a和b(b≠0)，若存在整数k，使得a=bk，我们称a能被b整除，记作b|a．此时把a叫做bŒ．的倍数，b叫做a的约数．如果a除以b的余数不为零，则称a不能被b整除，或b不整除a，记作b a 2．数的整除特征（1）1与0的特性：1是任何整数的约数，即对于任何整数a，总有1|a．0是任何非零整数的倍数，a≠0，a为整数，则a|0．（2）能被2，5；4，25；8，125；3，9；11，7，13整除的数的特征：能被2整除的数的特征：个位为0，2，4，6，8的整数能被2整除，我们记为2k(k为整数)．能被5整除的数的特征：个位数为0或5的整数必被5整除，我们记为5k(k为整数)．能被4、25整除的数的特征：末两位数字组成的两位数能被4（25）整除的整数必能被4（25）整除．能被8，125整除的数的特征：末三位数字组成的三位数能被8（125）整除的整数必能被8（125）整除．能被3，9整除的数的特征：各个数位上数字之和能被3或9整除的整数必能被3或9整除．能被11整除的数的特征：一个整数的奇数位数字之和与偶数位数字之和的差如果是11的倍数，则这个数就能被11整除．能被7，11，13整除的数的特征：一个三位以上的整数能否被7（11或13）整除，只须看这个数的末三位数字表示的三位数与末三位以前的数字组成的数的差（以大减小）能否被7（11或13）整除．3．整除的几条性质（1）自反性：a|a(a≠0)（2）对称性：若a|b, b|a，则a=b（3）传递性：若a|b, b|c，则a|c（4）若a|b, a|c，则a|(b, c)（5）若a|b, m≠0，则am|bm（6）若am|bm, m≠0，则a|b（7）若a|b, c|b, (a, c)=1，则ac|b高一·联赛班·第4讲·学生版2 二、带余除法对于任一整数a 及大于1的整数m ，存在唯一的一对整数q, r (0≤r<m)，使得a=qm+r 成立，这个式子称为带余除法式。

数学奥赛辅导 第二讲整除知识、方法、技能整除是整数的一个重要内容，这里仅介绍其中的几个方面：整数的整除性、最大公约数、最小公倍数、方幂问题.Ⅰ. 整数的整除性初等数论的基本研究对象是自然数集合及整数集合. 我们知道，整数集合中可以作加、减、乘法运算，并且这些运算满足一些规律（即加法和乘法的结合律和交换律，加法与乘法的分配律），但一般不能做除法，即，如b a ,是整除，0≠b ，则ba不一定是整数. 由此引出初等数论中第一个基本概念：整数的整除性.定义一：（带余除法）对于任一整数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,,|,|1n i Z c b c a b a i ni 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）如在等式∑∑===mk k ni i b a 11中除开某一项外，其余各项都是c 的倍数，则这一项也是c 的倍数.（8）n 个连续整数中有且只有一个是n 的倍数. （9）任何n 个连续整数之积一定是n 的倍数.本讲开始在整除的定义同时给出了约数的概念，又由上一讲的算术基本定理，我们就可以讨论整数的约数的个数了.定理一：设大于1的整数a 的标准分解式为n n p p p p p p a n <<<⋅= 211(21ααα为质数，i α均为非负整数），则a 的约数的个数为∏=+=ni i a d 1)1)(α（.所有的约数和为：∏=+--=ni ii p p a i 1111)(ασ. 事实上，由算术基本定理的推论知∏=+=ni i a d 1)1()(α，而各约数的和就是∏=+++ni i i ipa p 1)1( 展开后的各项之和，所以∏∏==--=+++=ni ni i i i p p p p a ii11111)1()(αασ 例如，25200=24·32·52·7，所以90)11)(12)(12)(14()25200(=++++=d ， 999441717151513131212)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 ni i n i i p p b p a ii(,11∏∏====βα为质数，i i a β,为非负整数），则∏==ni 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,111111212221111n 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） 1800（r 3）由定义和上述求法不难得出最大公约数和最小公倍数的如下性质：（1）),(),(,b a m bm am N m =∈则.（2）设b a c ,为的公约数，则.),(),(cb a cb c a =特别地，若1),(),,(==cbc 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∏∏==+==ni ni i i i iab p pi i 11),min(βαβα.（7）设na 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 均为自然数,使得.131911318131211+--+-= q p证明：p 可被1979整除. (第21届IMO 试题)【证明】)131814121(2)1319131211(+++-+++= q p =)6591211()1319131211(+++-++++=)99019891()131816611()131916601(++++++ =1979×)99098911318661113196601(⨯++⨯+⨯两端同乘以1319！得1319！*).(1979N m m qp∈⨯=⨯此式说明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 ，定义,),(112∑=-=nr k r k n F 求证：)1,(n F 可整除).,(k n F（1996加拿大数学竞赛试题）【证明】当m n 2=时，,)12()1,2(21∑=+==mr m m r m F∑∑+=-=-+=mm r k mr k rrk m F 2112112),2(],)12([)12(12112112112-=-=-=--++=-++=∑∑∑k mr k mr k mr 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([1212121112----=-++-+∑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 这21+k p 个数中任两个数的差是形如)11(2122221-≤≤+k k p a p p ap 的数,不能被21+k p 整除,故这21+k p 个数除以21+k p 后,余数两两不同.但除以21+k p 后的余数只有0，1，…，21+k p －1这21+k p 个，从而恰有一个数)1(2100+≤≤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 222210 k ，++n p p p t k 222210 （k +1）分别能被2122221,,+k k p p p p 整除，即1+=k m 时命题成立.故题对一切正整数m 均成立.例6：求证：.),)(,)(,(),,(],][,][,[],,[22a c c b b a c b a a c c b b a c b a = （第1届美国数学奥林匹克竞赛试题）【证明】设,,,111∏∏∏======ni ini ini ii p c i p b i p a γβα其中i p 为质数，i i i γβα,,为非负整数，则 ∏==ni i iiip c b a 1),,max(,],,[γβα∏==ni i i i p b a 1),max(,],[ βα∏=∏=ni i iiip c b a 1),,min(,),,(γβα∏==ni i iip b a 1),min(,),( βα因此只需证明2max(),m ax (),m ax (),m ax (),,i i i i i i i i i αγγββαγβα---=2min(),m in(),m in(),m in(),,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的质数，ba b a b a c pp +++=,(），试证：（1）1),(=a c ；（2）1=c 或.p c =（1985新加坡数学竞赛试题）【证明】由已知得),(,N s t cs ba b a ct b a pp ∈=++=+，两式相乘得,)(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：设∑=+=nk n k k S 175)(，求最大公约数).,(3n n S S d =（第26届IMO预选题）【解】能过具体计算可猜想.)2)1((2)21(244+=+++=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(444444+⨯+=++=k k k k k k k k d 由于12+k 和16+k 互质，所以).81,)12((244+=k k d 而当13+=t k 时13,)12(81)12(44+≠+=+t k t k 时，4)12(+k 与81互质.故此时有⎪⎪⎩⎪⎪⎨⎧≥++==+==⨯⨯=⨯=.)0(4666,812;26,8812812812444444t t t n n k t n n n k d 时或当时当 （2）当当12+=k n 时).)23)(12(3[2,)]1)(12[(2(44++++=k k k k d1,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(2444444时或当时当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 222118++是一个自然数的平方.（1980年第6届全俄数学竞赛试题）【证明】（1）当8≤n 时，)122(222118118++⋅++=--n n n N ，因（…）为奇数，所以要使N 为平方数，n 必为偶数.逐一验证8,6,4,2=n 知，N 都不是平方数. （2）当9=n 时，11222289118⨯=++=N 不是平方数.（3）当10≥n 时，)29(288-+=n N ，要N 为平方数，829-+n 应为奇数的平方，不妨假设829-+n =2)12(+k ,则).2()1(210+⨯-=-k k n 由于1-k 和2+k 是一奇一偶，左边为2的幂，因而只能1-k =1，于是得2=k ，由21022=-n 知12=n 为所求.。

数的整除性及性质数的整除性是指一个整数能够被另一个整数整除，即没有余数的除法运算。

整除性是数学中的一个重要概念，它有一些基本的性质。

性质1：如果一个整数能够被另一个整数整除，那么它也能够被这个整数的因子整除。

性质2：如果一个整数能够被两个整数整除，那么它也能够被这两个整数的公倍数整除。

性质3：如果一个整数能够被另一个整数整除，那么它的倍数也能够被这个整数整除。

性质4：如果一个整数能够被另一个整数整除，那么它的相反数也能够被这个整数整除。

性质5：如果一个整数能够被另一个整数整除，那么它的任意正整数倍也能够被这个整数整除。

性质6：如果一个整数能够被另一个整数整除，那么它的任意正整数加减这个整数也能够被这个整数整除。

性质7：如果一个整数能够被另一个整数整除，那么它的任意正整数乘以这个整数也能够被这个整数整除。

性质8：如果一个整数能够被另一个整数整除，那么它的任意正整数除以这个整数也能够被这个整数整除。

性质9：如果一个整数能够被另一个整数整除，那么它的任意正整数次方也能够被这个整数整除。

性质10：如果一个整数能够被另一个整数整除，那么它的倒数也能够被这个整数整除。

性质11：如果一个整数能够被另一个整数整除，那么它的相反数的倒数也能够被这个整数整除。

性质12：如果一个整数能够被另一个整数整除，那么它的任意正整数倍数的倒数也能够被这个整数整除。

性质13：如果一个整数能够被另一个整数整除，那么它的任意正整数加减这个整数的倒数也能够被这个整数整除。

性质14：如果一个整数能够被另一个整数整除，那么它的任意正整数乘以这个整数的倒数也能够被这个整数整除。

性质15：如果一个整数能够被另一个整数整除，那么它的任意正整数除以这个整数的倒数也能够被这个整数整除。

性质16：如果一个整数能够被另一个整数整除，那么它的任意正整数次方的倒数也能够被这个整数整除。

性质17：如果一个整数能够被另一个整数整除，那么它的相反数的次方也能够被这个整数整除。