下载文档原格式
华杯赛数论专题：余数及同余一、带余除法的定义：一般地，如果a是整数，b是整数（b≠0）,若有a÷b=q…r，也就是a＝b×q＋r, 0≤r＜b；我们称上面的除法算式为一个带余除法算式.这里：（1）当时：我们称a可以被b整除，记作b|a，q称为a除以b的商或完全商（2）当时：我们称a不可以被b整除，记作，q称为a除以b的商或不完全商二、同余的概念两个整数被同一个大于1的整数m除，所得的余数相同，就说这两个整数对于除数m来说是同余的.也可以换句话来说这个概念，如果两个整数的差能被大于1的整数m整除，那么这两个整数对于除数m来说是同余的.同余的概念和符号都是德国伟大数学家高斯引进的.一般地，两个整数a和b，除以大于1的正整数m，如果所得的余数相同，就说a、b对于模m同余，记作a≡b（mod m）.由于一个整数被m除的余数只能是0、1、2、3、…、m-1这m个数，所以全体整数可按被m除的余数分类，凡是余数相同的归为一类，全体整数就被划分成了m类，同一类中的任何两数被m除的余数都相等，即同一类中任何两数的差都能被m整除，不同类的任何两数被m除的余数都不相等.三、同余的性质1.如果a≡b（mod m），那么m|（a-b）；如果整数a和b对于模m是同余的，那么a 与b的差能被m整除.2.a≡a（mod m），即任何整数都与自身同余.3.若a≡b（mod m），则b≡a（mod m）.4.若a≡b（mod m），b≡c（mod m），则a≡c（mod m）.5.若a≡b（mod m），c≡d（mod m），则a+c≡b+d （mod m），a－c≡b－d （mod m），a×c≡b×d （mod m）.6.若a≡b（mod m），则an≡bn（mod m）。
（其中n为正整数）.例1.用一个两位数除708，余数为43，求这个两位数.【答案】95【解答】根据被除数-余数=商×除数，可知，所求两位数一定是707-43=665的大于43的约数，所以所求的两位数是95.例2.数713、1103、830、947被一个数除所得余数相同（余数不为0），求这个除数.【答案】39，13或3.【解答】1103－713=390=3×13×2×5，947－830=117=3×13×3，1103－947=156=2×13×3×2，除数为39，13或3.例3.从1、2、…100中最多能选出多少个数，使选出的数中每两个的和都不能被3整除？【答案】35【解答】1、2、…100中，除以3余1的数共34个，即1、4、7、10、…、100.除以3余2的数共33个，选出的数中，如果有除以3余1的，就一定不能有除以3余2的；如果有除以3余2的，也就不能有除以3余1的。
初中数学竞赛讲座——数论部分9（费马⼩定理）第9讲费尔马⼩定理⼀、基础知识：法国数学家费尔马在1640年提出了⼀个有关整数幂余数的定理，在解决许多关于某个整数幂除以某个整数的余数问题时⾮常⽅便有⽤，在介绍这个定理之前，我们先来看⼀些具体的同余式，请同学们注意观察，发现这些同余式符合什么规律．3≡1（mod 2），5≡1（mod 2），7≡1（mod 2）…22≡1（mod 3），42≡1（mod 3），52≡1（mod 3）…24≡1（mod 5），34≡1（mod 5），44≡1（mod 5）…26≡（23）2≡1（mod 7），36≡（33）2≡1（mod 7），46≡（43）2≡1（mod 7）…这些同余式都符合同⼀个规律，这个规律就是费尔马⼩定理．费尔马⼩定理：如果p是质数，（a，p）=1，那么a p－1≡1（mod p）与费马⼩定理相关的有⼀个中国猜想，这个猜想是中国数学家提出来的，其内容为：当且仅当2p-1≡1(mod p)，p是⼀个质数。
假如p是⼀个质数的话，则2p-1≡1(mod p)成⽴（这是费马⼩定理的⼀个特殊情况）是对的。
但反过来，假如2p-1≡1(mod p)成⽴那么p是⼀个质数是不成⽴的（⽐如341符合上述条件但不是⼀个质数）。
如上所述，中国猜测只有⼀半是正确的，符合中国猜测但不是质数的数被称为“伪质数”。
对于中国猜测稍作改动，即得到判断⼀个数是否为质数的⼀个⽅法：如果对于任意满⾜1 < b< p的b下式都成⽴：b p-1≡1(mod p)，则p必定是⼀个质数。
实际上，没有必要测试所有的⼩于p的⾃然数，只要测试所有的⼩于p的质数就可以了。
这个算法的缺点是它⾮常慢，运算率⾼；但是它很适合在计算机上⾯运⾏程序进⾏验算⼀个数是否是质数。
（⼀）准备知识：引理1．若a,b,c为任意3个整数，m为正整数，且(m,c)=1,则当ac≡bc(mod m)时，有a≡b(mod m)证明：ac≡bc(mod m)可得ac–bc≡0(mod m)可得(a-b)c≡0(mod m)因为(m,c)=1即m,c互质，c可以约去，a–b≡0(mod m)可得a≡b(mod m)引理2．若m为整数且m>1,a1,a2,a3,a4,…a m为m个整数，若在这m个数中任取2个整数对m不同余，则这m个整数对m构成完全剩余系。
同余理论在数学竞赛中的运用同余理论是数论中的一个重要分支，是指两个整数间差是一些给定的模数的倍数。
同余理论在数学竞赛中的运用非常广泛，无论是解题方法还是抽象思维训练都有涉及。
首先，同余理论可以用于解决一类问题，即同余方程问题。
同余方程是指一个未知数与模数之间具有其中一种特定关系的方程。
在数学竞赛中，我们经常会遇到需要求解同余方程的问题。
通过应用同余理论，可以利用模数的性质，简化问题的计算过程，从而较快地得到解。
举一个例子，假设一个问题是求解方程7x ≡ 6 (mod 5) 的整数解。
这个问题可以通过同余理论快速解决。
首先，我们可以观察到7 ≡ 2 (mod 5)。
因此，方程可以变形为2x ≡ 6 (mod 5)。
接下来，我们可以计算出 2 的逆元，即找到一个整数 a，满足2a ≡ 1 (mod 5)。
通过观察，我们可以发现 a = 3 是满足此条件的整数。
因此，将方程两边同时乘以 3，得到6x ≡ 18 (mod 5)。
再简化一步，可以得到x ≡ 3 (mod 5)。
因此，方程的整数解为 x = 3 + 5k，其中 k 是任意整数。
除了解同余方程的问题，同余理论还可以应用于解决循环问题。
在数学竞赛中，我们常常会遇到需要求循环节或重复周期的问题。
通过使用同余理论，我们可以很方便地进行分析和计算。
举一个例子，假设一个问题是求证序列{1^2, 2^2, 3^2, …,(p−1)^2} 在模 p 下的循环节长度。
首先，我们可以利用模数的性质，观察到对于任意整数 a 和 m，(a+m)^2 ≡ a^2 (mod m)。
因此，在这个问题中，我们只需要分析序列的前 p 个项即可。
进一步观察，我们可以发现p^2 ≡ 0 (mod p)，因此 p^2 不在序列中。
又因为 p-1 是模 p 的逆元，所以 (p-1)^2 ≡ 1 (mod p)。
因此，序列{1^2, 2^2, 3^2, …,(p−1)^2} 在模 p 下的循环节长度为 p-1此外，同余理论还可以用于计算和判定整数的性质。
初一竞赛班讲义——同余式（一）【数论背景】数论有它自己的代数，称为同余理论．最先引进同余的概念与记号的是数学王子高斯． 先看一个游戏：有n ＋1个空格排成一行，第一格中放入一枚棋子，甲乙两人交替移动棋子，每步可前移1，2或3格，以先到最后一格者为胜．问是先走者胜还是后走者胜？应该怎样走才能取胜？同余，顾名思义，就是余数相同．【定义讲解】定义1 给定一个正整数m ，如果用m 去除a ，b 所得的余数相同，则称a 与b 对模m 同余，记作(mod )a b m ≡并读作“a 同余b ，模m ”或读作“a 与b 对模m 同余”。
若a 与b 对模m 同余，由定义1，有12,a mq r b mq r =+=+所以 a -b=m(q 1-q 2)， 即 ()m a b - 反之，若()m a b -，设112212,,0,1a mq r b mq r r r m =+=+≤≤-则有12()m r r -．因｜r 1-r 2｜≤m -1，故r 1-r 2=0，即r 1＝r 2．于是，我们得到同余的另一个等价定义：定义2 若a 与b 是两个整数，并且它们的差a-b 能被一正整数m 整除，那么，就称a 与b 对模m 同余．同余式的写法，使我们联想起等式．其实同余式和代数等式有一些相同的性质，最简单的就是下面的定理1．定理1 (1)a ≡a(modm)．(2) 若a ≡b(modm)，则b ≡a(modm)．(3) 若a ≡b(modm)，b ≡c(modm)，则a ≡c(modm)．在代数中，等式可以相加、相减和相乘，同样的规则对同余式也成立．定理2 若a ≡b(modm)，c ≡d(modm)，则a ±c ≡b ±d(modm)，ac ≡bd(modm)．证 由假设得m ｜a -b ，m ｜c -d ，所以m ｜(a ±c)-(b ±d)， m ｜c(a -b)＋b(c -d)，即a ±c ≡b ±d(modm)，ac ≡bd(modm)．由此我们还可以得到：若a ≡b(modm)，k 是整数，n 是自然数，则a ±k ≡b ±k(modm)，ak ≡bk(modm)，a n ≡b n (modm)．★★★ 对于同余式ac ≡bc(modm)，我们是否能约去公约数c ，得到一个正确的同余式a ≡b(modm)？在这个问题上，同余式与等式是不同的．例如25≡5(mod 10)，约去5得5≡1(mod 10)．这显然是不正确的．但下面这种情形，相约是可以的．定理3 若ac ≡bc(modm)，且(c ，m)=1，则a ≡b(modm)．证 由题设知ac-bc=(a-b)c=mk．由于(m，c)=1，故m｜a-b，即a≡b(modm)．应用同余式的性质可以简捷地处理一些整除问题．若要证明m整除a，只需证a≡0(modm)即可．【例题分析】求余数是同余的基本问题．在这种问题中，先求出与±1同余的数是一种基本的解题技巧．例1(1)求33除21998的余数．(2)求8除72n+1-1的余数．例2求证：(1)8｜(551999＋17)；(2) 8(32n＋7)；(3)17｜(191000-1)．证例3求使2n-1为7的倍数的所有正整数n．例4 对任意的自然数n，证明A=2903n-803n-464n＋261n能被1897整除．例5任意平方数除以4余数为0和1(这是平方数的重要特征)．例6任意平方数除以8余数为0，1，4(这是平方数的又一重要特征)．。
第8讲数论（余数问题）1、带余除法的定义及性质：一般地，如果a是整数，b是整数（b≠0）,若有a÷b=q……r，也就是a＝b×q＋r,0≢r＜b；我们称上面的除法算式为一个带余除法算式。
这里：(1)当0r=时：我们称a可以被b整除，q称为a除以b的商或完全商；(2)当0r≠时：我们称a不可以被b整除，q称为a除以b的商或不完全商。
余数一定要比除数小。
2、三大余数定理：（1）余数的加法定理a与b的和除以c的余数，等于a,b分别除以c的余数之和，或这个和除以c的余数。
当余数的和比除数大时，所求的余数等于余数之和再除以c的余数。
（2）余数的乘法定理a与b的乘积除以c的余数，等于a,b分别除以c的余数的积，或者这个积除以c所得的余数。
当余数的和比除数大时，所求的余数等于余数之积再除以c的余数。
（3）同余定理若两个数a，b除以同一个数m得到的余数相同，则a，b的差一定能被m 整除用式子表示为：如果有a≡b ( mod m )，那么一定有a－b＝mk,k是整数，即m|(a－b)。
3、弃九法：任何一个整数模9同余于它的各数位上数字之和。
以后我们求一个整数被9除的余数，只要先计算这个整数各数位上数字之和，再求这个和被9除的余数即可。
（思考：有没有求一个整数被11除的余数的快速方法呢？）4、同余同补问题：例1：（1）用某自然数a去除1992，得到商是46，余数是r，求a和r。
（2）有两个自然数相除，商是17，余数是13，已知被除数、除数、商与余数之和为2113，则被除数是多少？练习：（1）甲、乙两数的和是1088，甲数除以乙数商11余32，求甲、乙两数；（2）用一个自然数去除另一个自然数，商为40，余数是16.被除数、除数、商、余数的和是933，求这2个自然数各是多少？例2：三个不同的自然数的和为2001，它们分别除以19,23,31所得的商相同，所得的余数也相同，这三个数是_______，_______，_______。
初中数学竞赛：数的整除（同余）【内容提要】一. 同余的概念 两个整数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 m c 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是三个互不相等的正整数.求证：a3b－ab3,b3c－bc3,c3a－ca3三个数中，至少有一个数能被10整除.证明：用同余式判定整除法证明当正整数n的个位数是0，1，4，5，6，9时，n3的个位数也是0，1，4，5，6，9.∴这时n3≡n (mod 10)；当正整数n的未位数为2，3，7，8时，n3的个位数分别是8，7，3，2.∵8与－2，7与－3，3与－7，2与－8，除以10是同余数，∴这时n3≡－n (mod 10)；把三个正整数a,b,c按个位数的情况，分为上述两类时，则至少有两个属于同一类.设a,b的末位数是同一类，那么a3b－ab3≡ab－ab≡0 (mod 10)；或a3b－ab3≡(－a)b－a(－b)≡0 (mod 10).∴10| (a3b－ab3)【练习】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).。
第7讲同余的概念及基本性质数论有它自己的代数，称为同余理论．最先引进同余的概念与记号的是数学王子高斯．先看一个游戏：有n＋1个空格排成一行，第一格中放入一枚棋子，甲乙两人交替移动棋子，每步可前移1，2或3格，以先到最后一格者为胜．问是先走者胜还是后走者胜？应该怎样走才能取胜？取胜之道是：你只要设法使余下的空格数是4的倍数，以后你的对手若走i格(i=1，2，3)，你走4-i格，即每一次交替，共走了4格．最后只剩4个空格时，你的对手就必输无疑了．因此，若n除以4的余数是1，2或3时，那么先走者甲胜；若n除以4的余数是0的话，那么后走者乙胜．在这个游戏里，我们可以看出，有时我们不必去关心一个数是多少，而要关心这个数用m除后的余数是什么．又例如，1999年元旦是星期五，1999年有365天，365=7×52＋1，所以2000年的元旦是星期六．这里我们关心的也是余数．这一讲中，我们将介绍同余的概念、性质及一些简单的应用．同余，顾名思义，就是余数相同．一、基础知识定义1 给定一个正整数m，如果用m去除a，b所得的余数相同，则称a与b对模m同余，记作a≡b(mod m)，并读作a同余b，模m．否则，就称a与b对于模m不同余，记作a≡b（mod m），根据定义，a与b是否同余，不仅与a、b有关，还与模m有关，同一对数a和b，对于模m同余，而对于模n也许就不同余，例如，5≡8（mod 3），而5≡8（mod 4），若a与b对模m同余，由定义1，有a=mq1＋r，b=mq2+r．所以a-b=m(q1-q2)，即m｜a-b．反之，若m｜a-b，设a=mq1＋r1，b=mq2＋r2，0≤r1，r2≤m-1，则有m｜r1-r2．因｜r1-r2｜≤m-1，故r1-r2=0，即r1＝r2．于是，我们得到同余的另一个等价定义：定义2 若a与b是两个整数，并且它们的差a-b能被一正整数m整除，那么，就称a 与b对模m同余．另外，根据同余的定义，显然有以下几种关系是成立的：⑴a≡a（mod n）⑵a≡b（mod m）⇔b≡a（mod n）⑶a≡b（mod n）⇒a≡c（mod m）b≡c（mod m）由此可见，同余是一种等价关系，以上这三条分别叫做同余的反射性，对称性和传递性，而等式也具有这几条性质．二、典型例题;例1．如果a≡b（mod m），以下命题正确的有哪些？请说明理由？⑴m | a－b⑵a = b+mt⑶a = k1m+ r1，b = k2m+ r2（0≤r1，r2＜m）⇔r1= r2解：⑴因a≡b（mod m），所以可得a = k1m+ r，b = k2m+ r，那么a－b=（k1－k2）m，由于k1－k2是整数，因此m | a－b是正确的．⑵根据⑴可得a－b= mt，即a= b+mt⑶根据⑴可得，m | r1－r2，又因为0≤| r1－r2 |＜m，所以| r1－r2 |=0，故r1= r2．例2．判断正误，并说明理由．⑴如果a≡b（mod m）那么ka≡kb（mod m）⑵如果a≡b（mod m），c是整数，那么a±c≡b±c (mod m)⑶如果a1≡b1（mod m），a2≡b2（mod m），那么a1±a2≡b1±b2 (mod m)，a1a2≡b1b2 (mod m)．⑷如果3a≡3b(mod 6 )，那么a≡b (mod 6 )解：⑴∵a≡b（mod m），∴m | a－b，∴m | k (a－b)即m | (ka－kb)∴ka≡kb（mod m）⑴成正确⑵∵a≡b（mod m），∴m | a－b又因为c是整数，所以m | a－c－b+c，即m | (a－c) －(b－c)即a－c≡b－c（mod m）同理可得，a+c≡b+c（mod m）⑶仿照上面的两个小题的方汪，可以判定这个命题也是正确的⑷显然6≡12(mod 6)，而2≡ 4 (mod 6)，因此，这个命题不正确说明：⑶的结论可以得到同余的另一条性质，即a≡b（mod m）⇒a n≡b n（mod m）此题说明两个同余式能够象等式一样进行加、减、乘、乘方，但同余式两边却不能除以同一数，那么，同余式的两边在什么情况下可以同除以一个数呢？我们先看下面的例题．例3．由下面的哪些同余式可以得到同余式a≡b（mod 5）①3a ≡3b （mod 5） ②10a ≡10b （mod 5）③6a ≡6b （mod 10） ④10a ≡10b （mod 20）解：①因3a ≡3b （mod 5），所以5 | 3（a －b ），而5 | 3 ，因此5 | a －b ，故a ≡b （mod 5）②由10a ≡10b （mod 5）可以得到5 | 10（a －b ），而5 | 10，因此5不一定整除a －b ，故a ≡b （mod 5）就成立③由6a ≡6b （mod 10）可得10 | 6（a －b ），而10=2×5，6=2×3，因此5 | a －b ， 故a ≡b （mod 5）成立④由10a ≡10b （mod 20）可得到20 | 10（a －b ），而20= 4×5，4 | 10，因此5 | (a －b )故a ≡b （mod 5）不成立综上所述，由3a ≡3b （mod 5）或6a ≡6b （mod 10）都可以得到a ≡b （mod 5）说明：在①中，因为（3，5）=1，因此由5 | 3（a －b ）一定可以得到5 | a －b ，进而得到a ≡b （mod 5），一般地，如果（k ，m ）=1，ka ≡kb （mod m ），那么a ≡b （mod m ）在③中，因（6，10）=2，因此由10| 6（a －b ）一定可以得到5 | a －b ，进而得a ≡b （mod 5），一般地，如果（k ，m ）= d ，ka ≡kb （mod m ），那么a ≡b )(mod dm ．例4．如果a ≡b （mod 12）且a ≡b （mod 8），那么以下同余式一定成立的是哪些？①a ≡b （mod 4） ②a ≡b （mod 24） ③a ≡b （mod 20） ④a ≡b （mod 48） 解：正确的有①和②①由题中的条件可得12 | a －b ，又因4 | 12，所以4 | a －b ，故a ≡b （mod 4）． ②因12 | a －b ，8| a －b ，所以a －b 是12和8的公倍数，又因为[8，12]=24，因此 a －b 必是24的倍数，即24 | a －b ，故a ≡b （mod 24）．③显然，当a = 26，b = 2时满足条件a ≡b （mod 12）和a ≡b （mod 8），但却不满足 a ≡b （mod 20）．④同③，用a = 26，b = 2验证即可．【说明】：⑴一般地，若a ≡b （mod m ）且n | m ，那么a ≡b （mod n ）⑵若a ≡b （mod m ），a ≡b （mod n ），那么a ≡b （mod [m ，n ]），它的一个特殊情况就是：如果a ≡b （mod m ），a ≡b （mod n ）且（m ，n ）=1，那么a ≡b （mod m n ）【一些结论】1.同余定义的等价形式①a ≡b （mod m ）⇔m | a －b②a ≡b （mod m ）⇔a = b +mt2．同余式的同加、同乘性如果a 1≡b 1（mod m ），a 2≡b 2（mod m ）那么⑴a 1±a 2≡b 1±b 2（mod m ）⑵ka 1≡kb 1（mod m ）（k ∈Z ）⑶a 1a 2≡b 1b 2（mod m ）⑷a 1n ≡b 1n （mod m ）（n 是整数）．3．如果（k ，m ）=d ，ka ≡kb （mod m ），那么a ≡b )(mod dm ． 这条性质的直接推论就是：如果（k ，m ）=1，ka ≡kb （mod m ），那么a ≡b （mod m ）4．如果a ≡b （mod m ）且n | m ，那么a ≡b （mod n ）5．如果a ≡b （mod m ），a ≡b （mod n ），那么a ≡b （mod [m ，n ]）这条性质的一个推论就是：如果a ≡b （mod m ），a ≡b （mod n ）且（m ，n ）=1，那么a ≡b （mod m n ）例5．⑴求19992002除以9的余数；⑵求1010除以7的余数解：⑴∵9 | 1999－1000，∴1999≡1000≡1（mod 9）∴19992000≡12002≡1（mod 9），∴19992000除以9的余数是1⑵∵10≡3（mod 7），∴103≡33≡－1（mod 7）∴106≡（－1）2≡1（mod 7），∴1010≡104（mod 7）又∵102≡9≡2（mod 7），∴102≡10 4≡22≡4（mod 7）所以1010除以7的余数是4．说明：求较大数的余数时，可先设法找到与±1同余的数，然后利用同余式的性质，求出所求数的余数．例6．求14589+32002除以13的余数．解：∵145≡2（mod 13），∴1456≡26≡－1（mod 13）∴（1456）14≡（－1）14≡1（mod 13）即14584≡1（mod 13）又∵1455≡25≡6（mod 13）所以14589≡14584·1455≡6×1≡6（mod 13）又∵33≡1（mod 13），∴（33）667≡32001≡1（mod 13），∴32002≡3（mod 13） 所以，14589+32002≡6+3≡9（mod 13）即14589+32002除以13的余数是9例7．求19982002的十位数字分析：此题可以通过19982002的末两位数来求解，与前面的方法类似解：∵199898≡－2（mod 100），∴19982002≡（－2）2002≡22002≡41001（mod 100） 因为4≡4（mod 100），42≡16（mod 100），43≡64（mod 100），44≡56（mod 100），45≡24（mod 100），46≡96（mod 100），47≡84（mod 100），48≡36（mod 100）， 49≡44（mod 100），410≡76（mod 100），411≡4（mod 100）…所以4 n 除以100的余数是以4、16、64、56、24、96、84、36、44、76周期性出现的，因41001=410×100+1，所以41001≡4（mod 100），因此19982002≡4（mod 100），故19982002的十位数字是0．说明：正整数幂的末位数、末两位数、末三位数都具有周期性．例8（1998年匈牙利奥林匹克竞赛题）求使2n +1能被3整除的一切自然数n . 解∵ ∴则2n +1∴当n 为奇数时，2n +1能被3整除；当n 为偶数时，2n +1不能被3整除.例9 求证31980+41981能被5整除.证明 ∵∴∴∴例10．求20032002的末位数字．分析：此题就是求20032002除以10的余数解：∵2003≡3（mod 10），∴20034≡34≡1（mod 10），∴20032002≡（20034）500·20033≡1500·33≡27≡7（mod 10）∴20022002的末位数字是7． 说明：对于十进制的整数011a a a a n n -有如下性质：)10(mod 0011a a a a a n n ≡- 例11．已知n 是正整数，证明48 | 72n ―2352n ―1证明：∵48=3×16，（3，16）=1∴只需证明3| 72n ―2352n ―1且16 | 72n ―2352n ―1即可∵7≡1（mod 3），2352≡0（mod 3）∴72n ―2352n ―1≡12n ―2352×0－1≡0（mod 3）∴3 | 72n ―2352n ―1，又∵2352=16×147，∴2352≡0（mod 16）∴72n ―2352n ―1≡49n －1≡1n －1≡0（mod 16）∴16 | 72n ―2352n ―1，所以48| 72n ―2352n ―1．说明：当模很大时，可以用本题的方法把问题化为较小的模来求解，请同学位用这个方法重解例8．例12．已知n是任意的正整数，且m | 7n+12n―1，求正整数m的最大值．解：设a n=7n+12n―1，那么，a1=7+12―1=18，a2=72+24―1=72∴（a1，a2）=（18，72）=18，∴m≤18，下面证明对任何正整数n，都有18 | 7n+12n―1又因为18=2×9，所以只须证明2 | 7n+12n，9 | 7n+12n―1即可．∵7≡1（mod 2），∴7n+12―1≡1n+0―1≡0（mod 2）即2 | 7n+12n―1，对n进行分类讨论，⑴若n≡0（mod 3），则n=3k（k为正整数）7n+12n―1≡73k+36k+1≡（―2）3k+0―1≡（―8）k―1≡1k―1≡0（mod 9）⑵若n≡1（mod 3），则n=3k+1（k为非负整数）7n+12n―1≡73k+36k+127+12―1≡0（mod 9）⑶若n≡2（mod 3），则n=3k+2（k为非负整数）7n+12n―1≡73k·72+36k+24―1≡72+24―1≡0（mod 9）因此，对一切自然数n，都有9 | 7n+12n―1．综上所述，18 | 7n+12n―1，因此m的最大值为18．例13 把1，2，3…，127，128这128个数任意排列为a1，a2，…，a128，计算出｜a1-a2｜，｜a3-a4｜，…，｜a127-a128｜，再将这64个数任意排列为b1，b2，…，b64，计算｜b1-b2｜，｜b3-b4｜，…，｜b63-b64｜．如此继续下去，最后得到一个数x，问x是奇数还是偶数？解因为对于一个整数a，有｜a｜≡a(mod 2)，a≡-a(mod 2)，所以b1＋b2＋…＋b64=｜a1-a2｜+｜a3-a4｜+…+｜a127-a128｜≡a1-a2＋a3-a4+…+a127-a128≡a1＋a2＋a3＋a4+…+a127＋a128(mod 2)，因此，每经过一次“运算”，这些数的和的奇偶性是不改变的．最终得到的一个数x≡a1＋a2＋…＋a128＝1＋2＋…＋128＝64×129≡0(mod 2)，故x是偶数．例14 求证：一个十进制数被9除的余数等于它的各位数字之和被9除的余数．10≡1(mod 9)，故对任何整数k≥1，有10k≡1k＝1(mod 9)．因此即A被9除的余数等于它的各位数字之和被9除的余数．说明(1)特别地，一个数能被9整除的充要条件是它的各位数字之和能被9整除．(2)算术中的“弃九验算法”就是依据本题的结论．三、模拟训练1求证：(1)8｜(551999＋17)；(2) 8(32n ＋7)；(3)17｜(191000-1)．证 (1)因55≡-1(mod 8)，所以551999≡-1(mod 8)，551999＋17≡-1＋17=16≡0(mod 8)，于是8｜(551999＋17)．(2)32=9≡1(mod 8)，32n ≡1(mod 8)，所以32n ＋7≡1＋7≡0(mod 8)，即8｜(32n ＋7)．(3)19≡2(mod 17)，194≡24=16≡-1(mod 17)，所以191000=(194)250≡(-1)250≡1(mod 17)，于是17｜(191000-1)．2．求20032002的末位数字分析：此题就是求20032002除以10的余数解：∵2003≡3（mod 10），∴20034≡34≡1（mod 10），∴20032002≡（20034）500·20033≡1500·33≡27≡7（mod 10）∴20022002的末位数字是7说明：对于十进制的整数011a a a a n n -有如下性质：011a a a a n n -)10(mod 0a ≡． 3求2999最后两位数码.解 考虑用100除2999所得的余数. ∵∴又∴∴ ∴2999的最后两位数字为88.4．求证：22000+1不能被7整数．分析：只需证明22000≡－1（mod 7）即可证明：∵26≡1（mod 7），∴22000≡（26）333·22≡1·22≡4（mod 7），∴22000+1≡5（mod 7）所以7 | 22000+15 对任意的自然数n，证明A=2903n-803n-464n＋261n 能被1897整除．证1897=7×271，7与271互质．因为2903≡5(mod 7)，803≡5(mod 7)，464≡2(mod 7)，261≡2(mod 7)，所以A=2903n-803n-464n+261n≡5n-5n-2n+2n=0(mod 7)，故7｜A．又因为2903≡193(mod 271)，803≡261(mod 271)，464≡193(mod 271)，所以故271｜A．因(7，271)=1，所以1897整除A．6 任意平方数除以4余数为0和1(这是平方数的重要特征)．证因为奇数2=(2k＋1)2=4k2＋4k+1≡1(mod 4)，偶数2=(2k)2=4k2≡0(mod 4)，所以7 任意平方数除以8余数为0，1，4(这是平方数的又一重要特征)．证奇数可以表示为2k＋1，从而奇数2=4k2＋4k+1=4k(k＋1)+1．因为两个连续整数k，k＋1中必有偶数，所以4k(k＋1)是8的倍数，从而奇数2=8t+1≡1(mod 8)，偶数2=(2k)2=4k2(k为整数)．(1)若k=偶数=2t，则4k2=16t2＝0(mod 8)．(2)若k=奇数=2t+1，则4k2=4(2t＋1)2=16(t2＋t)+4≡4(mod 8)，所以求余数是同余的基本问题．在这种问题中，先求出与±1同余的数是一种基本的解题技巧．8 形如F n＝22n+1，n=0，1，2，…的数称为费马数．证明：当n≥2时，F n的末位数字是7．证当n≥2时，2n是4的倍数，故令2n=4t．于是F n=22n＋1=24t+1=16t＋1≡6t＋1≡7(mod 10)，即F n的末位数字是7．说明费马数的头几个是F0＝3，F1＝5，F2＝17，F3＝257，F4＝65537，它们都是素数．费马便猜测：对所有的自然数n，F n都是素数．然而，这一猜测是错误的．首先推翻这个猜测的是欧拉，他证明了下一个费马数F5是合数．。
同 余同余是数论中的重要概念，也是一种方便有力的工具。
它主要涉及同余式、剩余类及鸥拉函数等内容。
一、 基本理论：1.同余式：a ≡b(modm) ⇔a=1q m+r 且b=2q m+r ⇔m ∣a-b （1） 自反性：a ≡a(modm)（2） 对称性：a ≡b(modm) ⇔b ≡a(modm)（3） 传递性：a ≡b(modm)且b ≡c(modm)，则a ≡c(modm)（4） a ≡b(modm)，c ≡d(modm)，则a ±c ≡b ±d(modm)，ac ≡bd(modm)（5） a ≡b(modm)，n +∈Z ，则nn b a ≡ (modm) （6） a ≡b(modm)，m=qn ，n +∈Z ，则a ≡b(modn)（7） a ≡b(mod i m )，i =1、2、…k ，则a ≡b(mod[k m m m ,,21])（8） m ≥1，m +∈Z ，(a,m)=1，则∃c ，使ac ≡1(modm)2．剩余类i M ={i+km ∣i=1,2,…m-1,k ∈ Z}称为模m 的剩余类（同余类），表示为imodm.(1) 在任意给定的m+1个整数中，必有两个对模m 同余。
(2) 存在m 个数，两两对模m 不同余。
(3) n ∣m ，则Z r ∈∃，有rmodm ⊆rmodn(4) 1a modm=2a modm ，则(1a ，m)=(2a ，m)(5) f(x)=011a x a x a n n n n +++-- ， g(x)= 011b x b x b n n n n +++-- ，是两整系数多项式，若满足i i b a ≡(modm)(i=1,2…n)，则当a ≡b(modm)时，f(a)=g(b)(modm)。
（上述多项式叫同余多项式，记为f(x) ≡g(x)(modm)3．鸥拉函数(r,m)=1，则称rmodm 为模m 的既约（互素）同余类，模m 的所有既约同余类的个数记作Ф(x),叫鸥拉函数。
第8讲剩余系及其一次同余方程一、基础知识：（1）剩余系对于任意正整数n而言，一个整数除以m所得的余数只能是0,1,2, …,n-1中的某一个。
依次可将整数分成n个类（例如n＝2时，就是奇数或偶数），从每一类中各取一个数所组成的集合就称为模的一个完全剩余系，简称为模的完系。
定义1：如果一个剩余系中包含了这个正整数所有可能的余数（一般地，对于任意正整数n，有n个余数：0,1,2,...,n-1），那么就被称为是模n的一个完全剩余系。
定义2：剩余系：设模为m,则根据余数可将所有的整数分成m类，分别记成[0],[1],[2],…[m-1]，这m个数{0,1,2,…m-1}称为一个完全剩余系，每个数称为相应类的代表元。
例如：当m=10则,{0,1,2,3,4,5,6,7,8,9} 最小非负完全{-5,-4,-3,-2,-1,0,1,2,3,4} 绝对值最小{-4,-3,-2,-1,0,1,2,3,4,5} 绝对值最小（一）根据剩余类的概念，很容易得到以下几条有关剩余类的性质：①每一个整数一定包含在而且仅包含在模m的一个剩余类中②整数p所属的模m的剩余类中的每一个数都可以写成km+p的形式，这里k是整数用符号p mod m表示p所属的模m的剩余类，这条性质写成数学表达式就是p mod m= {p+km（k是整数）}③整数p、q在模m的同一个剩余类中的充要条件是p、q对模m同余。
这条性质用数学符号就可表示为：p mod m= q mod m p≡q（mod m）实际上，同余式就是剩余类等式的一个特殊情况，是集合中的一个元素，前面有关同余的一些性质对剩余类仍然成立。
这条性质表明，对于模m的两个剩余类要么相等，要么它们的交集为空集，因此，模m有且仅有m个剩余类，它们是：0mod m，1 mod m，2 mod m，…（m―1）mod m。
在解决一些有关模m余数的问题时，我们就可以查看m个数：0，1，2，…，m―1，从而得相应的剩余类的情况，使问题变得异常简单，具体例子，请看后面的例题。
④在任意取定的m+1个整数中，必有两个整数对模m同余。
（二）根据同余式的性质，我们很容易得到剩余系的其它一些性质：⑤m个整数x1，x2，…，x m是模m的一组完全剩余系的充要条件是x1，x2，…，x m 中的任意两个数对模m都不同余。
⑥如果x1，x2，…，x m是模m的一组完全剩余系，那么对任意的整数c，x1+c，x2+c，…，x m+c也是模m的一组完全剩余系。
⑦设k1，k2，…，k m是m个整数，如果x1，x2，…，x m是模m的一组完全剩余系，那么x1+k1m，x2+k2m，…，x m+k1m也是模m的一组完全剩余系。
（2）一次同余方程设m | a，则ax≡b（mod m）叫做模m的一次同余方程。
如果x= x0是方程ax≡b（mod m）的一个解，那么x= km+x0也是这个方程的一个解。
这是因为，如果ax0≡b（mod m），那么一定有akm+ax0≡b（mod m），即a(km+x0) ≡b （mod m），这说明如果x=x0是方程ax≡b（mod m）的一个解，那么剩余类x0mod m中的任何一个数也是这个方程的解，这些解都看作是相同的，把剩余类x0mod m称为同余方程ax≡b（mod m）的一个解，记作x≡x0（mod m）因此，我们在解同余方程的时候，只需在任意取定的模m的一组完全剩余系中求解模m的同余方程，就可获得这个方程的全部解。
二、典型例题：例1．求证：一定存在整数n，使4n2+27n―12能被5整除，并求出这些数。
分析：可以选模5的一个完全剩余系逐个验算，只要数a使4a2+27a―12能被15整除，那么剩余类a mod 5中的任何一个整数也满足条件。
解：取模5的一个完全剩余系0，1，2，3，4直接计算可知，3和4满足条件，所以使4n2+27―12能被5整除的所有的整数是n≡3（mod 5）和n≡4（mod 5）。
例2 求使2n-1为7的倍数的所有正整数n．解因为23≡8≡1(mod 7)，所以对n按模3进行分类讨论．(1) 若n=3k，则2n-1＝(23)k-1＝8k-1≡1k-1＝0(mod 7)；(2) 若n=3k＋1，则2n-1=2·(23)k-1=2·8k-1≡2·1k-1＝1(mod 7)；(3) 若n=3k＋2，则2n-1=22·(23)k-1=4·8k-1≡4·1k-1＝3(mod 7)．所以，当且仅当3｜n时，2n-1为7的倍数．例3．m、p、n为自然数，求证：3 | n p（n2m+2）分析：对n按模3进行分类讨论证明：⑴当n≡0（mod 3）时，n p≡0（mod 3），∴n p（n2m+2）≡0（mod 3）⑵当n≡1（mod 3）时，n p≡1（mod 3），n2m≡12m≡1（mod 3），∴n p（n2m+2）≡1·（1+2）≡3≡0（mod 3）⑶当n≡2（mod 3）时，n p≡2 p（mod 3），n2m≡（n2）m≡4m≡1m≡1（mod 3）∴n p（n2m+2）≡2 p（1+2）≡2 p·0≡0（mod 3）所以，对一切自然数n，都有3 | n p（n2m+2）例4.分别求满足下列条件的最小自然数：（1）用3除余1，用5除余1，用7除余1。
（2）用3除余2，用5除余1，用7除余1。
（3）用3除余1，用5除余2，用7除余2。
（4）用3除余2，用7除余4，用11除余1。
思路分析：（1）该数减去1以后，是3，5和7的最小公倍数105，所以该数的是105+1=106（2）该数减去1以后是5和7的公倍数。
因此我们可以以5和7的公倍数中去寻找答案。
下面列举一些同时被5除余1，被7除余1的数，即1，36，71，106，141，176，211，246，……从以上数中寻找最小的被3除余2的数。
36≡0（mod3），71≡2（mod3），符合条件的最小的数是71。
（3）我们首先列举出被5除余2，被7除余2的数，2，37，72，107，142，177，212，247，……从以上数中寻找最小的被3除余1的数。
2（mod3），37≡（mod3）、因此符合条件的最小的数是37。
（4）我们从被11除余1的数中寻找答案。
1，12，23，34，45，56，67，78，89，100，133，144，155，166，177，188，199，210，232，243，……1（mod3）； 1（mod7），不符合12≡0（mod3）， 12≡5（mod7）不符合23≡2（mod3）， 23≡2（mod7）不符合34≡1（mod3）， 34≡6（mod7）不符合45≡0（mod3）， 45≡3（mod7）不符合56≡2（mod3）， 56≡0（mod7）不符合67≡1（mod3）， 67≡4（mod7）不符合78≡0（mod3）， 78≡1（mod7）不符合89≡2（mod3）， 89≡5（mod7）不符合100≡1（mod3）， 100≡2（mod7）不符合122≡2（mod3）， 122≡3（mod7）不符合133≡1（mod3）， 133≡0（mod7）不符合144≡1（mod3）， 144≡4（mod7）不符合155≡2（mod3），155≡1（mod7）不符合166≡1（mod3），166≡5（mod7）不符合177≡0（mod3），177≡2（mod7）不符合188≡2（mod3），188≡6（mod7）不符合199≡1（mod3），199≡3（mod7）不符合210≡0（mod3），210≡0（mod7）不符合221≡2（mod3），221≡4（mod7）符合因此符合条件的数是221。
例5.现有70个数排成一行，除了两头的两个数以外，每个数的三倍恰好等于它两边两个数的和，这一行最左边的几个数是这样的：0，1，3，8，21，……，问这一行数最右边的一个数被6除的余数是几？分析：如果将这70个数一一列出，得到第70个数后，再用它去除以6得余数，总是可以的，但计算量太大。
即然这70个数中：中间的一个数的3倍是它两边的数的和，那么它们被6除以后的余数是否有类似的规律呢？0，1，3，8，21，55，144，……被6除的余数依次是0，1，3，2，3，1，0，……结果余数有类似的规律，继续观察，可以得到：0，1，3，2，3，1，0，5，3，4，3，5，0，1，3，2，3，……可以看出余数前12个数一段，将重复出现。
70÷2=5……10，第六段的第十个数为4，这便是原来数中第70个数被6除的余数。
例6．解下列同余方程⑴3x ≡2（mod 6） ⑵4x ≡6（mod 10）解：⑴当x ≡0（mod 6）时，3x ≡0（mod 6）当x ≡1（mod 6）时，3x ≡3（mod 6）当x ≡2（mod 6）时，3x ≡6≡0（mod 6）当x ≡3（mod 6）时，3x ≡9≡3（mod 6）当x ≡4（mod 6）时，3x ≡12≡0（mod 6）当x ≡5（mod 6）时，3x ≡15≡3（mod 6）所以方程3x ≡2（mod 6）无解。
⑵与⑴小题类似，取模10的最小完全剩余系0，1，2，3，…，9直接计算可知，x =4和x =9是方程的解，所以这个同余方程的解为x ≡4（mod 10）或x ≡9（mod 10）说明：①解模m 的一次同余方程，可以取模m 的一个完全剩余系直接计算，这个方法也适用于其它的同余方程。
②模m 的一次同余方程ax ≡b （mod m ）（m |a ）有解的充要条件是（a ，m ）| b 。
例7. 同余方程2x ≡6（mod 8）的解和方程x ≡3（mod 4）的解是否相同，说明理由。
解：设x =x 0是方程2x ≡6（mod 8）的一个解，那么2x 0≡6（mod 8）∴2x 0=8 k +6，x 0= 4k +3，∴x 0≡3（mod 4）即方程2x ≡6（mod 8）的解必是方程x ≡3（mod 4）的解反之，若x =x 0是方程x ≡3（mod 4）的一个解，那么x 0≡3（mod 4）∴x 0= 4m +3，∴2x 0=8m +6，故2x 0≡6（mod 8）即方程x ≡3（mod 4）的解必是方程2x ≡6（mod 8）的解所以，方程2x ≡6（mod 8）和x ≡3（mod 4）的解相同说明：若正整数d | （a ，b ，m ），则方程ax ≡b （mod m ）的解与方程d b x d a )(mod d m 的解相同，利用这条性质可以将较大模数的同余方程化为较小模数的同余方程。
例8．解同余方程38x ≡－19（mod 95）分析：此题中的模95的剩余数太多，如果选定一个完全剩余系进行直接计算，运算量相当大，因此我们可以运用上题的方法，将模化小一点。
