竞赛讲座 整数的整除性和同余

初中数学竞赛教程《同余3》同余是数论中一个重要的概念，也是初中数学竞赛中常考的知识点之一、同余关系可以帮助我们解决一些整数求余的问题，同时也有一些重要的应用，如模运算、同余方程等。

本文将介绍同余的基本概念、性质以及应用。

一、同余的基本概念同余的定义：设a、b为任意两个整数，m为一个正整数，如果m整除(a-b)，则称a与b对于模m同余，记作a≡b(mod m)，读作a与b模m 同余。

二、同余的性质1. 自反性：对于任意整数a，有a≡a(mod m)。

证明：因为m整除（a-a），所以a与a对于模m同余。

2. 对称性：若a≡b(mod m)，则b≡a(mod m)。

证明：由a≡b(mod m)，得m整除a-b，又由整除的性质，得m整除-(a-b)，即m整除b-a，所以b≡a(mod m)。

3. 传递性：若a≡b(mod m)，b≡c(mod m)，则a≡c(mod m)。

证明：由a≡b(mod m)和b≡c(mod m)，得m整除a-b和b-c所以m整除（a-b）+（b-c），即m整除a-c，所以a≡c(mod m)。

三、同余的应用1. 求余数：当m=10时，对一个正整数n，n≡a(mod 10)的意义就是n的个位数是a。

比如，1234≡4(mod 10)。

2. 模运算：同余关系可以推广到任意的四则运算和乘幂运算中。

比如，对于任意整数a、b，若a≡b(mod m)，那么对于任意整数c，有(a+c)≡(b+c)(mod m)和(a-c)≡(b-c)(mod m)。

另外，如果a≡b(mod m)，则a^k≡b^k(mod m)。

3. 同余方程：同余方程是指形如ax≡b(mod m)的方程，其中a、b、m是已知的整数，x是未知的整数。

同余方程在密码学、计算机算法等领域有广泛的应用。

解同余方程的方法一般有试错法、中国剩余定理等。

在解同余方程时，我们要先求出模m意义下的倒数，一般记作b^-1，满足b*b^-1≡1(mod m)。

同余理论及其应用基础知识一. 定义定义1. 设m 为正整数，整数a 和b 之差可被m 整除时，称为a 和b 关于模m 同余，记作 ).(mod m b a ≡ 定义2. 被正整数m 除余数相等的所有整数的集合称为模m 的剩余类。

模m 的剩余类共有m 个。

定义3. 在模m 的m 个剩余类中各取一个整数作为代表，这些代表的集合称为模m 的完全剩余系。

定义4. 绝对值不超过]2[m 的模m 的完全剩余系称为模m 的绝对最小剩余系。

定义5. 当模m 的某一剩余类的所有整数均与m 互素时，则称此剩余类是模m 的简化类。

模m 的简化类共有)(m φ个。

定义6. 在模m 的)(m φ个简化类中各取一个整数作为代表，这些代表的集合称为模m 的简化剩余系。

定义7. 欧拉函数：设n 为正整数，从1到n 的整数中与n 互素的整数的个数用)(n φ表示，称)(n φ为欧拉函数。

当1212s s np p p ααα=时，有)11)...(11)(11()(21s p p p n n ---=φ 二. 定理定理1. ).(mod m b a ≡ 的必要充分条件是a 和b 被m 除的余数相等。

定理 2. I .);(mod m a a ≡II .若),(mod m b a ≡则);(mod m a b ≡III .若),(mod m b a ≡),(mod m c b ≡则).(mod m c a ≡定理3. 若)(m od 11m b a ≡，)(m od 22m b a ≡，则I .)(m od 2121m b b a a +≡+；II .(mod 2121m b b a a -≡-2 )(m od 212m b b a -≡-；III .)(m od 2121m b b a a ≡.定理4. 如果),...,2,1)((m od n i m b a i i =≡，则I .)(m od ......2121m b b b a a a n n +++≡+++；II . ).(m od ......2121m b b b a a a n n ≡推论. 如果).(mod m b a ≡n 为任意正整数，则).(mod m b a nn ≡ 定理5. 如果).(mod m cb ca ≡则).),((modm c m b a ≡ 推论. 如果1),(=m c ，).(mod m cb ca ≡则).(mod m b a ≡ 定理6. 如果).(mod m b a ≡则).,(),(m b m a =定理7. a 和b 属于模m 的同一剩余类的充要条件是).(mod m b a ≡定理8. m 个整数m a a a ,...,,21是模m 的完全剩余系的充要条件是m a a a ,...,,21关于模m 两两互不同余。

初中数学竞赛讲座-数论部分2（整数的整除性）第二讲整数的整除性一、基础知识：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，∴bap,cbq（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，∴bap,caq(b,q是整数），∴bcapaqa(pq)，∴a|(bc)性质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．性质8n个连续整数中，必有一个能被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，且存在整数某，y，使得a某+by=1，证明：ab|n．初中数学兴趣班系列讲座——数论部分唐一良数学工作室证明：由条件，可设n=au，n=bv，u，v为整数，于是n=n(a某+by)=na某+nby=abv某+abuy=ab(v某+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若某，y为整数，且2某+3y，9某＋5y之一能被17整除，那么另一个也能被17整除．证明：设u=2某＋3y，v=9某＋5y．若17｜u，从上面两式中消去y，得3v-5u=17某．①所以17｜3v．因为(17，3)=1，所以17｜v，即17｜9某＋5y．若17｜v，同样从①式可知17｜5u．因为(17，5)=1，所以17｜u，即17｜2某＋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 被整数m(m≥1)除的余数相同,则称a 同余于b 模m,或a,b 对模m 同余.记为a≡b(modm).余数r:0≤r<1.2. 性质：(ⅰ)a≡b(modm)⇔m|a-b,即a=b+mk,k ∈Z.(ⅱ)若a≡b(modm),b≡c(modm),则a≡c(modm).(ⅲ)若a 1≡b 1(modm),a 2≡b 2(modm)，则a 1±a 2≡b 1±b 2(modm),a 1a 2≡b 1b 2(modm);(ⅳ)设f(x)=a n x n +a n-1x n-1+…+a 1x+a 0,g(x)=b n x n +b n-1x n-1+…+b 1x+b 0是两个整系数多项式,满足a i ≡ b i (modm)(0≤i≤n).若a≡b(modm),则f(a)≡f(b)(modm).(ⅴ)ac≡bc(modm)⇔a≡b(mod ),(m c m ), (ⅵ)若m≥1,(a,m)=1,则存在整数c 使得ac≡1(modm).称c 为a 对模m 的逆或倒数,记为c=a -1(modm);(ⅶ)⎩⎨⎧≡≡)(mod )(mod 21m b a m b a 同时成立⇔≡a b (mod[m 1,m 2]);(ⅷ)若a≡b(modm 1),a≡b(modm 2),且(m 1,m 2)= 1,则a≡b(modm 1m 2).3. 剩余类：设m 为正整数，把全体整数按对模m 的余数分成m 类，相应m 个集合记为：K 0,K 1,…,K m-1,其中K r ={qm+r|q ∈Z,0≤余数r≤m -1}称为模m 的一个剩余类。

性质：(ⅰ)i m i K Z 10-≤≤= 且K i ∩K j =φ(i≠j).(ⅱ)每一整数仅在K 0,K 1,…,K m-1一个里.(ⅲ)对任意a 、b ∈Z ，则a 、b ∈K r ⇔a≡b(modm).4. 完全剩余系：设K 0,K 1,…,K m-1为模m 的全部剩余类，从每个K r 里任取一个a r ，得m 个数a 0,a 1,…,a m-1组成的数组，叫做模m 的一个完全剩余系。

第二十六讲整数整除的概念和性质对于整数和不为零的整数b，总存在整数m，n使得a＝bm+n(0≤n<b)，其中m称为商，n称为余数，特别地，n＝0时，即a＝bm，便称a被被b整除(也称a是b的倍数或的约数)，记为b|a．整除有以下基本性质：1．若a|b，a|c，则a|（b c）；2．若a|b，b|c，则a|c；3．若a| b c，且(a，c)=1，则a|b，特别地，若质数p|b c，则必有p|b或p|c；4．若b|a，c|a，且(b，c) =1，则b c|a．解整除有关问题常用到数的整除性常见特征：1．被2整除的数：个位数字是偶数；2．被5整除的数：个位数字是0或5；3．被4整除的数：末两位组成的数被4整除；被25整除的数，末两位组成的数被25整除；4．被8整除的数：末三位组成的数被8整除；被125整除的数，末三位组成的数被125整除；5．被3整除的数：数字和被3整除；6．被9整除的数：数字和被9整除；7．被11整除的数：奇数位数字和与偶数位数字和的差被11整除．【例1】一个自然数与13的和是5的倍数，与13的差是6的倍数，则满足条件的最小自然数是．思路点拨略(重庆市竞赛题)注：确定已知条件来确定自然数，是数学活动中常见的一类问题，解这类问题时往往用到下列知识方法：(1)运用整除性质；(2)确定首位数字；(3)利用末位数字；(4)代数化；(5)不等式估算；(6)分类讨论求解等．【例2】有三个正整数a、b、c其中a与b互质且b与c也互质，给出下面四个判断：①(a+c)2不能被b整除，②a2+c2不能被b整除：③(a+b)2不能被c整除；④a2+b2不能被c整除，其中，不正确的判断有( )．A．4个B．3个 C 2个D．1个思路点拨举例验证．(“希望杯”邀请赛试题)1287xy是72的倍数，求出所有的符合条件的7位数．【例3】已知7位数6(江苏省竞赛题)1287xy能被8，9整除，运用整数能被8、9整除的性质求出x，y的思路点拨7位数6值．【例4】(1)若a、b、c、d是互不相等的整数，且整数x满足等式(x一a)(x一b)(x一c)(x一d)一9＝0，求证；4︳(a+b+c+d)．(2)已知两个三位数abc与def的和abc+def能被37整除，证明：六位数abcdef也能被37整除．思路点拨 (1)x 一a ，x 一b ，x 一c ，x 一d 是互不相等的整数，且它们的乘积等于9，于是必须把9分解为4个互不相等的因数的积；(2)因已知条件的数是三位数，故应设法把六位数abcdef 用三位数的形式表示，以沟通已知与求证结论的联系．注：运用整除的概念与性质，建立关于数字谜中字母的方程、方程组，是解数学谜问题的重要技巧．华罗庚曾说：“善于‘退’，足够地，‘退’，‘退’到最原始而不失去重要性的地方，是学好数学的一个诀窍．”从一般退到特殊，从多维退到低维，从空间退到平面，从抽象退到具体……只要不影响问题的求解，对于许多复杂的问题，以退求进是一种重要的解题思想．【例5】 (1)一个自然数N 被10除余9，被9除余8，被8除余7，被7除余6，被6除余5，被5除余4，被3除余2，被2除余1，则N 的最小值是 ．(北京市竞赛题)(2)若1059、1417、2312分别被自然数x 除时，所得的余数都是y ，则x —y 的值等于( )．A ．15B ．1C ．164D ．174(“五羊杯”竞赛题)(3)设N=个1990111，试问N 被7除余几?并证明你的结论． (安徽省竞赛题) 思路点拨 运用余数公式，余数性质，化不整除问题为整除问题．(1)N+1能分别被2，3，4，5，6，7，8，9，10整除，(2)建立关于x ，y 的方程组，通过解方程组求解，(3)从考察11，111，…111111被7除的余数人手．【例6】盒中原有7个球，一位魔术师从中任取几个球，把每一个小球都变成了7个小球，将其放回盒中，他又从盒中任取一些小球，把每一个小球又都变成了7个小球后放回盒中，如此进行，到某一时刻魔术师停止取球变魔术时，盒中球的总数可能是( )A ．1990个B ．1991个C 1992个D ．1993个思路点拨 无论魔术师如何变，盒中球的总数为6k+7个，其中k 为自然数，经验证，1993=331×6+7符合要求．故选D ．【例7】在100以内同时被2、3、5整除的正整数有多少个?思路点拨 由于2与3互质，3与5互质，5与2互质(这种特性我们也称为2、3、5两两互质)，所以同时被2、3、5整除的整数必然被2×3×5=30整除；另—方面，被30整除的正整数必然可同时被2、3、5整除，因此，在100以内同时被2、3、5整除的正整数就是在100以内被30整除的正整数，显然只有30、60、90三个．【例8】某商场向顾客发放9999张购物券，每张购物券上印有一个四位数的号码，从0001到9999号，如果号码的前两位数字之和等于后两位数字之和，则称这张购物券为“幸运券”．证明：这个商场所发放的购物券中，所有的幸运券的号码之和能被101整除． 思路点拨 显然，号码为9999是幸运券，除这张外，如果某个号码n 是幸运券，那么号m=9999—n 也是幸运券，由于9是奇数，所以m ≠n ．由于m+n=9999相加时不出现进位，这就是说，除去号码9999这张幸运券外，其余所有幸运券可全部两两配对，而每一对两个号码之和均为9999，即所有幸运券号码之和是9999的整倍数，而101│9999，故知所有幸运券号码之和也能被101整除思考：“如果某个号码n 是幸运券，那么号m=9999—n 也是幸运券”，这是解决问题的关键，请你考虑这句话合理性． 若六位数9381ab 是99的倍数，求整数a 、b 的值．81ab能被9整除，∴8+1+a+b+9+3=21+a+b能被9整除，得3+a+b=9k l(k1为整∵93数)．①81ab能被11整除，∴8—1+a—b+9—3=13+a—b能被11整除，得2+a—b=11k2(k2又93为整数)．②∵0≤a，b≤9 ∴0≤a+b≤18，－9≤a－b≤9．由①、②两式，得3≤<9k1≤21，－7≤11k2≤1l，知k1=1，或k1=2；k2=0，或，而3+a+b与2+a—b的奇偶性相异，而k1=2，k2=1不符合题意．故把k1=1，k2=0代人①、②两式，解方程组可求得a=2，b=4．【例9】写出都是合数的13个连续自然数．思路点拨方法一：直接寻找从2开始，在自然数2，3，4，5，6，…中把质数全部划去，若划去的两个质数之间的自然数个数不小于13个，则从中取13个连续的自然数，就是符合要求的一组解，例如：自然数114，115，116，…，126就是符合题意的一组解．方法二：构造法我们知道，若一个自然数a是2的倍数，则a+2也是2的倍数，若是3的倍数，则a+3也是3的倍数，…，若a是14的倍数，则a+14也母14的倍数，所以只要取a为2，3，…，14的倍数，则a+2，a+3，…a+14分别为2，3，…，14的倍数，从而它们是13个连续的自然．所以，取a=2×3×4×…×14，则a+2，a+3，…，a+14必为13个都是合数的连续的自然数．【例10】已知定由“若大于3的三个质数a、b、c满足关系式20+5b=c，则a+b+c是整数n的倍数”．试问：这个定理中的整数n的最大可能值是多少?请证明你的结论．思路点拨先将a+b+c化为3(a+2b)的形式，说明a+b+c是3的倍数，然后利用整除的性质对a、b被3整除后的余数加以讨论得出a+2b也为3的倍数．∵=a+b+2a+5b=3(a+2b)，显然，3│a+b+c若设a、b被3整除后的余数分别为r a、r b，则r a≠0，r b≠0．若r a≠r b，则r a=2，r b=1或r a=1，r b=2，则2a+5b =2(3m+2)+5(3n+1)=3(2m+5n+3)，或者2a+5b=2(3p+1)+5(3q+2)；3(2P+59+4)，即2a+5b为合数与已知c为质数矛盾．∴只有r a=r b，则r a=r b=1或r a=r b=2．于是a+2b必是3的倍数，从而a+b+c是9的倍数．又2a+5b=2×11十5×5=47时，=a+b+c=11+5+47=63，2a+5b =2×13十5×7=61时，a+b+c =13+7+61=81，而(63，81)=9，故9为最大可能值．注：由余数切入进行讨论，是解决整除问题的重要方法．【例11】一个正整数N的各位数字不全相等，如果将N的各位数字重新排列，必可得到一个最大数和一个最小数，若最大数与最小数的差正好等于原来的数N，则称N为“新生数”，试求所有的三位“新生数”．思路点拨将所有的三位“新生数”写出来，然后设出最大数、最小数，求差后分析求出所有三位“新生数”的可能值，再进行筛选确定．【例12】设N 是所求的三位“新生数”，它的各位数字分别为a 、b 、c (a 、b 、c 不全相等)，将其各位数字重新排列后，连同原数共得6个三位数：cba cab bca bac acb abc ,,,,,，不妨设其中的最大数为abc ，则最小数为cba ．由“新生数”的定义，得N=abc —cba =(100a+l0b+c)一(100c+l0b+d)=99(a —c)．由上式知N 为99的整数倍，这样的三位数可能为：198，297，396，495，594，693，792，891，990．这九个数中，只有954－459=495符合条件，故495是唯一的三位‘新生数”． 注：本题主要应用“新生数”的定义和整数性质，先将三位“新生数”进行预选，然后再从中筛选出符合题意的数。

- 1 -数学奥赛辅导----数论（2） 同余知识、方法、技能同余是数论中的重要概念，同余理论是研究整数问题的重要工作之一.本讲介绍同余的基本概念，基本性质. 1．设m 是一个给定的正整数，如果两个整数a 与b 用m 除所得的余数相同，则称a 与b 对模m 同余，记作)(mod m b a ≡，否则，就说a 与b 对模m 不同余，记作)(mod m b a ≡，显然，)(|)(,)(mod b a m Z k b km a m b a -⇔∈+=⇔≡；每一个整数a 恰与1，2，……，m ，这m 个数中的某一个同余； 2.同余的性质：1).反身性：)(mod m a a ≡；2).对称性：)(mod )(mod m a b m b a ≡⇔≡； 3).若)(mod m b a ≡，)(mod m c b ≡则)(mod m c a ≡;4).若)(mod 11m b a ≡，)(mod 22m b a ≡，则)(mod 2121m b b a a ±≡± 特别是)(mod )(mod m k b k a m b a ±≡±⇔≡；5).若)(mod 11m b a ≡，)(mod 22m b a ≡，则)(mod 2121m b b a a ≡； 特别是)(mod ),(mod m bk ak Z k m b a ≡⇔∈≡则 )(mod ),(mod m b a N n m b a nn≡⇔∈≡则； 6).)(mod )(m ac ab c b a +≡+；7).若)(mod 1),(),(mod m b a m c m bc ac ≡=≡时，则当 )(m o d )(m o d ).(mod ),(m b a mc bc ac dmb a d mc ≡⇔≡≡=特别地，时，当； 8).若)(mod 1m b a ≡，)(mod 2m b a ≡ )(mod 3m b a ≡……………… )(m o d n m b a ≡，且)(mod ],,[21M b a m m m M n ≡⋯⋯=，则3.完全剩余系：一组数y 1,y 2,…,y s 满足：对任意整数a 有且仅有一个y j 是a 对模m 的剩余，即a ≡y j (mod m )，则y 1,y 2,…,y s 称为模m 的完全剩余系。

第十七章 整数问题一、常用定义定理1．整除：设a,b ∈Z,a ≠0，如果存在q ∈Z 使得b=aq ，那么称b 可被a 整除，记作a|b ，且称b 是a 的倍数,a 是b 的约数。

b 不能被a 整除，记作a b.2.带余数除法：设a,b 是两个给定的整数，a ≠0，那么，一定存在唯一一对整数q 与r ，满足b=aq+r,0≤r<|a|，当r=0时a|b 。

3．辗转相除法：设u 0,u 1是给定的两个整数，u 1≠0，u 1 u 0,由2可得下面k+1个等式：u 0=q 0u 1+u 2,0<u 2<|u 1|； u 1=q 1u 2+u 3,0<u 3<u 2； u 2=q 2u 3+u 4,0<u 4<u 3； …u k-2=q k-2u 1+u k-1+u k ,0<u k <u k-1； u k-1=q k-1u k+1,0<u k+1<u k ； u k =q k u k+1.4．由3可得：（1）u k+1=(u 0,u 1)；（2）d|u 0且d|u 1的充要条件是d|u k+1；（3）存在整数x 0,x 1，使u k+1=x 0u 0+x 1u 1.5．算术基本定理：若n>1且n 为整数，则k ak aap p p n 2121=，其中p j (j=1,2,…,k)是质数（或称素数），且在不计次序的意义下，表示是唯一的。

6．同余：设m ≠0,若m|(a-b)，即a-b=km ，则称a 与b 模同m 同余，记为a ≡b(modm)，也称b 是a 对模m 的剩余。

7．完全剩余系：一组数y 1,y 2,…,y s 满足：对任意整数a 有且仅有一个y j 是a 对模m 的剩余，即a ≡y j (modm)，则y 1,y 2,…,y s 称为模m 的完全剩余系。

8．Fermat 小定理：若p 为素数，p>a,(a,p)=1，则a p-1≡1(modp)，且对任意整数a,有a p≡a(modp).9．若(a,m)=1，则)(m aϕ≡1(modm),ϕ(m)称欧拉函数。

初中数学竞赛：数的整除（同余）【内容提要】一. 同余的概念同余的概念两个整数a 和b 被同一个正整数m 除，所得的余数相同时，称a, b 关于模m 同余.记作a ≡b(mod m).如：8和15除以7同余1，记作8≡15(mod 7), 读作8和15关于模7同余. ∵2003=7×286+1，∴2003≡1 (mod 7)；∵－7和6对于模13同余6（余数是非负数）（余数是非负数）∴－7≡6（mod 13）；∵35和0除以5，余数都是0（即都能整除）（即都能整除）∴35≡0（mod 5）.二. 用同余式判定数的整除用同余式判定数的整除若a ≡b(mod m)， 则m|(a －b).即a －b ≡0(mod m)Ûm|(a －b).例如：11≡25(mod 7)Û7|(25－11)； 或7|(11－25). ∵25+35≡2+3≡0 (mod 5)，∴5|25+35.三. 同余的性质同余的性质(注意同余式与等式在变形中的异同点) 1. 传递性：传递性：)(m o d )(m o d )(m o d mc a m c b m b a ºÞþýüºº. 2. 可加可乘性：îíìº+º+Þþýüºº).(mod )(mod ).(mod )(mod m bd ac m d b c a m d c m b a ；， 推论推论可移性：a ≡b+c (mod m)Þ(a －b)≡c(mod m). 可倍性：a ≡b(mod m)Þka ≡kb(mod m)(k 为正整数). 可乘方：a ≡b(mod m)Þ a n ≡b n (mod m)(n 为正整数). 3. 当d 是a, b, m 的正公因数时，的正公因数时， a ≡b(mod m)Þd b d a º(mod dm ). 如：2是20，26，6的正公因数，的正公因数， 20≡26(mod 6)1310ºÞ(mod 3). 四. 根据抽屉原则：任给m+1个整数，其中至少有两个数对于模m 同余.即至少有两个，其差能被m 整除.例如：任给5个数a, b, c, d, e.其中至少有两个，它们的差能被4整除.∵除以4的余数只有0，1，2，3四种.∴5个数除以4至少有两个同余.【例题】例1. 已知：69，90，125除以正整数n 有相同的余数.求：n 的值的值解：∵69≡90(mod n)，90≡125(mod n). ∴ n|(90－69)，n|(125－90). 而21,35的最大公约数是7， 记作(21,35)=7(7是质数). ∴n=7例2. 求388除以5的余数.解：∵38≡3 (mod 5)，∴388≡38≡(32)4≡(－1)4≡1 (mod 5).(注意注意9除以5余4，－1除以5也是余4，∴32≡－1 (mod 5)例3. 求997的个位数字.解：解： ∵74k+n 与7n 的个位数字相同，的个位数字相同，且9≡1 ( mod 4)， ∴99≡19 ≡1(mod 4). ∴997与71的个位数字相同都是7.例4. 求证：7|(22225555+55552222).证明：∵22225555+55552222=(22225)1111+(55552)1111∵2222=7×317+3 ，5555=7×793+4. ∴2222≡3 ( mod 7)；5555≡4 (mod 7). ∴22225≡35≡5(mod 7)；55552≡42≡2 (mod 7). ∴22225+55552≡5+2≡0 ( mod 7).即22225≡－55552(mod 7). ∴(22225)1111≡(－55552)1111≡－(55552)1111 (mod 7).∴22225555+55552222≡0 (mod 7).∴7|(22225555+55552222).例5. 求使32n －1能被5整除的一切自然数n.解：∵32≡－1 (mod 5) ，∴(32)n ≡(－1)n (mod 5). 32n －1≡(－1) n －1(mod 5) ∵当且仅当n 为偶数时，(－1) n －1=0.∴使32n －1能被5整除的一切自然数n 是非负偶数是非负偶数例6. 已知：a, b, c 是三个互不相等的正整数.求证：a 3b －ab 3, b 3c －bc 3, c 3a －ca 3三个数中，至少有一个数能被10整除.证明：用同余式判定整除法证明证明：用同余式判定整除法证明当正整数n 的个位数是0，1，4，5，6，9时，n 3的个位数也是0，1，4，5，6，9.∴这时n 3≡n (mod 10)； 当正整数n 的未位数为2，3，7，8时，n 3 的个位数分别是8，7，3，2.∵8与－2，7与－3，3与－7，2与－8，除以10是同余数，是同余数，∴这时n 3≡－n (mod 10)；把三个正整数a, b, c 按个位数的情况，按个位数的情况，分为上述两类时，分为上述两类时，则至少有两个属于同一类.设a, b 的末位数是同一类，那么的末位数是同一类，那么a 3b －ab 3≡ab －ab ≡0(mod 10)；或a 3b －ab 3≡(－a)b －a(－b)≡0 (mod 10). ∴10| (a 3b －ab 3)【练习】1. 三个数33，45，69除以正整数N 有相同余数，但余数不是0，那么N=_______.2. 求777的个位数字.3. 求379245除以19的余数；的余数；41989除以9的余数. 4. 求19891990÷1990的余数.5. 四个数2836，4582，5164，6522都被同一个正整数除，所得的余数都相同且不是都被同一个正整数除，所得的余数都相同且不是 0，求除数和余数.6. 求证：7|(33334444+44443333).7. 已知：正整数n>2 . 求证：31111º 个n (mod 4).8. 任给8个整数，其中必有两个，它们的差能被7整除，试证之.9. 求使2n +1能被3整除的一切自然数n.10. 已知已知 69，90，125除以N (N>1) 有同余数，有同余数，那么对于同样的那么对于同样的N ，81同余于() （A ）3. （B ）4. （C ）5. （D ）7. （E ）8.【答案】1. N=12，6，2.(舍去3，∵余数是0).解法仿例1.2. 个位数字是3.∵7≡－1(mod 4), ∴ 777≡(－1)77(mod 4)……仿例33. 余数是18和1. ∵37≡－1 (mod 19) ∴原式≡－1 ≡18 (mod 19)；41989=(43)663 64≡1(mod 9) 64663≡1663 ≡1.4. 余数是1. ∵1989≡－1 (mod 1990) ∴19891990≡(－1)1990≡1 (mod 1990).5. 根据题意根据题意 2836≡4582≡5164≡6522≡r (mod m)而且4582－2836=1746, 6522－5164=1358.∴ m| 1746, 且m|1358， (1746，1358)=2×97∴m=194, 97, 2 (2不合题意.舍去)答：除数为194， 余数是120或除数为97， 余数是236. ∵ 33334444+44443333≡14444+(－1)3333≡0 (mod 7).7. 个个211111111-=n n 00+11≡11≡3 (mod 4).8. 8个正整数分别除以7，必有两个或两个以上是同余数，必有两个或两个以上是同余数9. ∵2≡－1 (mod 3) ∴2n ≡(－1)n (mod 3)2n +1≡(－1)n+1 (mod 3)当且仅当n 奇数时, (－1)n +1≡0 ∴能被3整除的一切正整数n 是奇数是奇数 10. (B).。

数论定理一. 知识要点1. 欧拉定理和费尔马小定理缩系的定义：设m 为正整数，一个模m 的剩余类称为与模m 互素的余类，如果它中的数与m 互素．在与模m 互素的各个剩余类中分别取一个代表所构成的集合称为模m 的一组缩系．很显然，缩系具有以下性质：（1）模m 的缩系中含有ϕ（m ）个数（ϕ（m ）是小于m 的正整数中且与m 互素的个数）．（2）设()m r r ϕ ,1是ϕ（m ）个与m 互素的整数，则()m r r ϕ ,1模m 两两不同余．（3）设()1,=m a ，且()m r r ϕ ,1是模m 的一组缩系，则()m ar ar ar ϕ,,,21 是模m 的一组缩系．欧拉（Euler ）定理：设m 是大于1的整数，a 为整数，且()1,=m a ，则()()m a m mod 1≡ϕ．For personal use only in study and research; not for commercial use解：设()m x x x ϕ,,,21 是模m 的缩系．因为()1,=m a ，所以()m ax ax ax ϕ,,,21 也是模m 的缩系．这两个缩系分别乘起来得()()()m x x x ax ax ax m m mod ·2121ϕϕ ≡，且()()1,21=m x x x m ϕ ．从而()()m a m mod 1≡ϕ )()m a m mod 1≡ϕ．特别地，取m 为质数p ，有费尔马（Fermat ）小定理：设p 为质数，a 为整数，p a ，则()p a p mod 11≡-．它也常常写成()p a a p mod ≡．这里不需假定p a ，但p 应为素数．For personal use only in study and research; not for commercial use2. 中国剩余定理（孙子定理）中国剩余定理：设k m m m ,,21是两两互质的正整数，k a a a ,,,21 是任意整数，则同余方程组()()()⎪⎪⎩⎪⎪⎨⎧≡=≡.mod ,mod ,mod 2211k k m a x m a x m a x 对模k m m m 21有唯一解． 解：设()k i m m m m M iki ,,2,121 ==．依题设，有()1,=i i m M ，由裴蜀定理知，存在整数i b ，使得()i i i m b M mod 1≡，k i ,2,1=．对k k k M b a M b a M b a x +++= 222111，其中i i i M b a 能被k i i m m m m ,,,,111+-整除，而被i m 除的余数恰为i a ．从而∑==ki i i i M b a x 1是同余方程组的解．又设x ，y 均为同余方程组的解，则有y x m -1，y x m -2，…，y x m k -，即y x m m m k - 21，亦即()k m m m y x 21mod ≡．所以同余方程组对模k m m m 21有唯一解．3. 威尔逊（wilson ）定理威尔逊（wilson ）定理：设p 为质数，则()()p p mod 1!1-≡-．解：对于任意整数a ，且1≤a ≤p －1，由裴蜀定理知，存在整数a ’，使得()p aa mod 1'≡．称a ’为a 的数论倒数，且不妨设1≤a ’≤p －1．若有整数b ，满足()p ba mod 1'≡，则将此式两边同乘以a ，有()p a b mod ≡．这说明对于不同整数a ，1≤a ≤p －1，对应着不同的数论倒数a ’．又若整数a 的数论倒数是它自身，则()p a a mod 1≡⋅，亦即()()()p a a mod 011≡-+，故1≡a 或()p mod 1-．当2=p 时，显然有()()p p mod 1!1-≡-．当p ＞2时，有2，3，…，p －2这p －3个数恰好配成互为数论倒数的23-p 对数，故它们的积()()p p p mod 1123223≡≡-⨯⨯⨯- ．于是()()()p p p mod 1111!1-≡-⨯⨯≡-．4. 拉格朗日定理设p 为质数，n 是非负整数，多项式()01a x a x a x f n n +++= 是一个模p 为n 次的整系数多项式（即p a n ），则同余方程()()p x f mod 0≡ （※），至多有n 个解（在模p 的意义下）．证明：我们对n 用归纳法．当0=n 时，()0a x f =，因为p a 0，故同余方程（※）无解，命题成立．设当l n =时命题成立，则当1+=l n 时，若命题不成立，即同余方程（※）至少有2+l 个解，设为()p c c c x l mod ,,,221+≡ ①，我们考虑多项式()()()()()11111111c x a c x a c x a c f x f l l l l l l -++-+-=-+++ )()111c x a c l l-++- ()()()()x h c x x a c x l l 111-=+-=+ ②，其中()x h 是l 次多项式并且首项系数1+l a ，满足1+l a p ，从而由归纳假设知l 次同余方程()()p x h mod 0≡ ③，至多有个l 个解，但由①，②可知同余方程③至少有l ＋1个解．()p c c c x l mod ,,,232+≡ ，矛盾！故当1+=l n 时命题成立．综上所述，命题得证．二. 典型例题例1. 已知正整数k ≥2，k p p p ,,,21 为奇质数，且()1,21=k p p p a ．证明：()()()111121----k p p p a 有不同于k p p p ,,21的奇质因数．证明：由()1,21=k p p p a ，有()1,1=p a ．由费尔马小定理，()11mod 11p ap ≡-．又k ≥2，p p p ,,,32 k p p p ,,,32 为奇质数，则()()()211121---k p p p 为正整数，从而()()()()12111mod 121p ak p p p ≡--- ，即()()()12111121----k p p p ap .同理，()()()1211121--⋯--k p p p a能被P 2，P 3，…P k 整除，从而()()()1211121+-⋯--k p p p a不能被k p p p p ,,,,321 整除．注意到()()()211121---k p p p 是一个偶数，则()()()0211121≡---k p p p a或1（mod4），因此4不整除()()()1211121+---k p p p a，故()()()1211121+---k p p p a异于k p p p ,,,21 的奇质因数．所以()()()()()()⎪⎪⎭⎫ ⎝⎛-=-------1121111112121k k p p p p p p a a()()()⎪⎪⎭⎫⎝⎛+---1211121k p pp a有异于k p p p ,,,21 的奇质因数．例2. 对于自然数n ，如果对于任何整数a ，只要1-n a n ，就有12-na n ，则称n 具有性质P ．（34届IMO预）（1）求证：每个素数n 都具有性质P ． （2）求证：有无穷多个合数也都具有性质P ．证：（1）设p n =为素数且1-p a p ，于是()1,=p a ．由费尔马小定理知11--p a p ，而()()1111-+-=--a a a a p p ．故1-a p ，即()p a m o d 1≡．因此，()p a i mod 1≡，1,,2,1,0-=p i ．上述p 个同余式累和，得()p p a a a p p mod 0121≡≡++++-- ．故()()11212++++---a a a a p p p ，即12-pa p ．（2）设n 是具有性质P 的合数．若1-na n ，则()1,=a n ．由欧拉定理，有()()n a n mod 1≡ϕ，又因()n a n mod 1≡，由阶的性质知，()()()n a n n mod 1,≡ϕ．如果()()1,=n n ϕ，则()n a mod 1≡，于是利用（1）中证明可得12-na n ．因此，问题化为求无穷多个合数n ，使()()1,=n n ϕ．对任何素数p ≥5，取p －2的素因数q ，并令pq n =．这时()()()11--=q p n ϕ．因为()2-p q ，所以q (p －1)．又因q ≤p －2＜p ，故p (q －1)．因此，有()()1,=n n ϕ．对于每个这样的合数n ，若()1-na n ，则()1-a n ，因而()n a k mod 1≡，,2,1,0=k ．故()12-n a n ．因为对于每个素数p ≥5都可按上述程序得到具有性质P 的相应合数()p n ，且p ＜()p n ＜p 2，所以，有无穷多个合数n 具有性质P ．例3. 求所有整数n ≥2，满足：对所有的整数a ，b ，且()()1,,==n b n a ，()n b a mod ≡的充分必要条件是()n ab mod 1≡．（第41届IMO 预选题）解：若n 有奇素因子p ，设n p a||，记1n p n a⋅=，N a ∈．由中国剩余定理知，存在Z x ∈，使()n x mod 1≡，()a p x mod 2≡，则()1,=n x ．取x b a ==，即知()n x mod 12≡，从而()a p mod 14≡，故3=p ，且1=a ．因此()1,5=n ．取5==b a ，即知()n mod 125≡，从而24n ，故,12,8,6,4,3,2=n 24,12,8,6,4,3,2．下证：当n 取上述值时，满足条件．注意到，当2 a 时，有()8mod 12≡a ；当3 a 时，有()3mod 12≡a ，又24n ，32243⨯=，故必有()n a mo d 12≡（因为()1,=n a ）．对Z b a ∈,，且()()1,,==n b n a ，()n b a mod ≡，则()n ab mod 1≡．对Z b a ∈,，且()()1,,==n b n a ， ()n ab mod 1≡，则()n ab a mod 12≡≡．从而()a b a n -又()1,=n a ，有()b a n -，即()n b a mod ≡．综上，所求n 的值为2，3，4，6，8，12，24．例4. 求所有正整数n ，满足对所有的正整数n ，存在一个整数m ，使12-n是92+m 的因子．（第39届IMO 预选题）解：引理1：若p 为4k －1（k ≥2）型质数，则不存在Z m ∈，使()p m mod 92-≡．证明：设)p m m mod 31≡()p m m mod 31≡（∵()13,=p ，∴m 1存在），N m ∈1．又∵()p m mod 912-≡, ∴)(mod 121p m -≡．由费马小定理知，()()()p m m p p p mod 11121212111-=-≡=≡---，矛盾．引理2：当1≤i ＜j 时，有()112,1222=++ji )112,12=++j，且()13,122=+i ．证明：∵()()()()12mod 211121222222+≡+-≡+=+--i i j ij ij ，∴()()12,1212,12222=+=++ij i )()12,1212,122=+=++i j．又∵()()3mod 2111222≡+-≡+i i ，∴()()13,23,122==+i．对于原题，若()()9122+-m n，n ≥2．设t n S ⋅=2，2 t ．若t ≥3，则()()1212-+n t ，从而()()9122+-m t ．又必存在4k －1型素数p ，且3≠p ，()12-tp （否则，()4mod 1111121≡⨯⨯⨯≡-≡- t ，矛盾）．此时()92+m p ，与引理1矛盾．故t =1，从而S n 2=，且()()()1212123121212222+++⋅=--S S．由引理2及中国剩余定理知，存在N m ∈1，使()()12m o d 22211+≡-ii m ，i =1，2，…，s －1．故()((2m o d0121222211≡+≡+-i m )()()12mod 0122221+≡+≡-ii ．令13m m =，有()()()12mod 013922122-≡+=+Sm m ．因此，()()9122+-m n ．综上，所求正整数n 为2的幂次2i （i =1，2，…）．数论中存在性问题是最常见的，除了运用数论存在性定理来解决外，还需要有直接构造的能力．例5. 证明：每个正有理数能被表示成3333d c b a ++的形式，且其中a ，b ，c ，d 是正整数．（40届IMO 预选题）证明：设该正有理数为p ．（1）当⎪⎭⎫⎝⎛∈2,21p 时，()()()()333321121p p p p p -++-++=，其中2p －1，2－p ，p ＋1+∈Q ．（2）当p ≥2时，由于⎪⎭⎫ ⎝⎛∈⎪⎭⎫ ⎝⎛1,41323，故有N n ∈，使⎪⎭⎫ ⎝⎛∈⋅⎪⎭⎫ ⎝⎛2,21323p n，由（1）有333333333322132132213223⎪⎪⎭⎫ ⎝⎛⎪⎭⎫ ⎝⎛-+⎪⎪⎭⎫ ⎝⎛+⎪⎭⎫ ⎝⎛⎪⎪⎭⎫ ⎝⎛-⎪⎭⎫ ⎝⎛⋅+⎪⎪⎭⎫ ⎝⎛+⎪⎭⎫ ⎝⎛⋅⎪⎭⎫ ⎝⎛=p p p p p n n n n n ．（3）当⎥⎦⎤ ⎝⎛∈21,0p 时，由于()4,1233∈⎪⎭⎫ ⎝⎛，故有N n ∈，使⎪⎭⎫ ⎝⎛∈⋅⎪⎭⎫ ⎝⎛2,21233p n ，由（1）有333333333232123123212332⎪⎪⎭⎫ ⎝⎛⎪⎭⎫ ⎝⎛-+⎪⎪⎭⎫ ⎝⎛+⎪⎭⎫ ⎝⎛⎪⎪⎭⎫⎝⎛-⎪⎭⎫ ⎝⎛⋅+⎪⎪⎭⎫ ⎝⎛+⎪⎭⎫ ⎝⎛⋅⎪⎭⎫ ⎝⎛=p p p p p n n n n n ．综上，总有+∈Q d c b a m 1111,,,,，使()()31313131313131313d c mb ma d c b a m p ++=++⋅=,设ma 1，mb 1，c 1，d 1的分母公倍数为n ，则取N mna a ∈=1，N mnb b ∈=，N nc c ∈=1，N nd d ∈=1，且3333dc b a p ++=．结论成立． 说明：这里是直接构造证明，首先发现恒等式()()()()333321121p p p p p -++-++=，进一步对p ≥2，或0＜p ≤21构造．例6. 证明：不存在非负整数k 和m ，使得()mk k ！14848+=+．证明：注意到0=k 或0=m 时，上述不定方程无解，于是，可设满足上述方程的k ，m 为正整数．（1）若1+k 为合数，设pq k =+1，2≤p ≤q ，注意到，应有48 | k ！．故k≥6，于是1＜2p ≤k ，故（1+k ）| k ！，进而（1+k ）| 48，结合1+k ≥7，可知1+k =8，12，24或48，分别代入，两边约去48后，可得矛盾．（2）若1+k 为质数，由威尔逊定理，可知k ！()1mod 1+-≡k ，于是，1+k | 47，进而1+k =47，这要求46！＋48=48×47m ①，从而m ＞1，两边除以48可知m 47148!46=+，两边模4，可知()()4mod 11≡-m ，故m 为偶数．设m =2k ，则由①可知2()()14714748!46+-=k k ，由232 |48!46，而()23mod 2147≡+k，故232 | 147-k，利用二项式定理()()223mod 146123247+≡+⨯=k k，从而23 | k ，进而m ≥46，这时，①式右边比左边大．矛盾．注：一般地，若n ＞4，且n 为合数，则n |（n －1）！，依此可以证明威尔逊定理的逆定理也成立． 例7. 设p 是质数，证明：存在一个质数q ，使得对任意整数n ，数p n p-不是q 的倍数．（第44届IMO 试题）证明：由于()212mod 1111p p p p p p p p p +≡++++=--- ．则11--p p p 中至少有一个质因子q ，满足q 对2p 的模不等于1。