第九讲同余（一）我们已经学过整除的概念和带余数的除法：被除数=除数×商+余数。在生活中，人们也经常关心“余数”。让我们看一个问
题：2015年12月1日是星期二，问20年后的12月1日是星期几？由于每年有365天，20年里有20×365=7300天.
但每4年有一个闰年，20年里有5个闰年，所以20年有7305天。7305=7×1043+4，说明20年中有1043周，外加4天。
我们关心的其实不是20年中有多少周，而是“外加的4天”（换句话说，关心的不是商，而是余数），因此20年后的12月1日是应该是星
期六。再看一个题目：一个奇数去除288和510所得的两个余数相同且都为29，求这个余数。如果从“被除数=除数×商+余数”这个
式子出发，必有“被除数–余数=除数×商”.可以知道288–29和510–29都是除数的倍数，即259和481都是除数的倍数。
或者说除数是259和481的公约数。用辗转相除法求259和481的最大公约数：481=259×1+222；259=222×
1+37；222=37×6.所以37双481和259的最大公约数。即37为我们要求的这个除数。验证一下：288=37×7
+29；510=37×13+29。结果是正确的。换一个角度考虑：由于288和510被同一个奇数除所得得余数相同，那么510和2
88的差就一定是这个奇数的倍数（求差时，相同的余数被减掉了）。因为510–288=222=2×3×37。所求的奇数是222的奇
数约数，只可能是37或111。但510=111×4+66；288=111×2+66。余数虽然相同但不是29，所以111不能是
所求的奇数。而510=37×13+29；288=37×7+29，所以37为所求的奇数。一．同余的概念像510和288这两个数
，被37除所得的余数相同（都是29），我们称510和288对于“模”37同余。“对于模37同余”就是指被37除所得的余数相同，
记为510≡288（mod37），这里mod37读作“模37”，“≡”读作“同余于”。一般地，两个整数a和b，除以一个大于1
的自然数n所得的余数相同，就称a和b对于模n同余或a和b在模n下同余，记为a≡b(modn)。有时也可以简读作a与b同余，这时
只是未将模n读出而已，很明显一谈到同余总是与模有关。很容易看到，所有的偶数在模2下彼此同余，所有的奇数在模2下也是彼此同余。这
里实际上是用2来将整数分成了两类，一类被2整除（余数为0），另一类被2除余数为1。偶数：0、2、4、6、……、2k、……；奇数：1
、3、5、7、……、2k+1、……。(k为整数)如果用4来将整数分类，由于余数可以为0、1、2、3共四种，因此可以分为四类：
0、4、8、12、……、4k、……；1、5、9、……、4k+1、……；2、6、10、……、4k+2、……；3、7、11、……
、4k+3、……。(k为整数)同一类的数被4除的余数是相同的，也就是说在模4下同余。如8≡16（mod4）；5≡17（
mod4）；2≡14（mod4）；6≡10（mod4）。因此对于每月的1号、8号、15号、22号、28号来说，1号是星期几，其
他几天也是星期几。它们是在模7下同余。二．同余的几条简单的性质性质1：任何整数都和自己同余，（这条性质称为自反性）a≡a（mo
dn）；性质2：甲、乙两个整数，如果甲和乙同余，那么乙和甲也同余。（这条称为对称性）若a≡b（modn），则b≡a（mod
n）。性质3：甲、乙、丙三个整数，如果甲和乙同余，乙和丙同余，那么甲和丙也同余。（这条称为传递性）。若a≡b(modn)，b
≡c(modn)，则a≡c(modn)。性质4：甲和乙同余，丙和丁同余，那么甲和丙的和与乙和丁的和一定同余（这条称为可加性）。
甲和丙的差与乙和丁的差一定同余（这条称为可减性）。甲和丙的乘积与乙和丁的乘积一定同余（这条称为可乘性）。若a≡b（modn
），c≡d（modn），则a+c≡b+d（modn），a–c≡b–d（modn），a×c≡b×d（modn）。特别是当
a≡b（modn），c=d时，上面的式子也成立，写作，则a+c≡b+c（modn），a–c≡b–d（modn），a×c≡b
×c（modn）。性质5：甲和乙同余，那么甲和乙的同次乘方的结果仍然同余。若a≡b（modn），则am≡bm（modn）
。以上的各条性质和等式的性质非常相似，不过同余式终究不是等式，并不是等式的各种性质都能移到同余式中来使用。注意同余式中不能随便
使用同除性，即在同余式ac≡bc（modn）两端，如果同除以c之后可能不同余。例如10≡6（mod4），两边同除以2，会得到
5≡3（mod4），这是错误的。例1．求437×309×1993被7除的余数。解：可以将437×309×1993先计算出来，再用
7来除，得到余数。但是计算量比较大。用同余来计算：437≡3(mod7)；309≡1(mod7)；1993≡5(mod
7)；利用同余式的可乘性，将三式相乘得437×309×1993≡3×1×5（mod7）≡15（mod7）≡1（mo
d7），所以437×309×1993被7除的余数是1。例2．70个数排成一行，除了两头的两个数之外，每个数的三倍恰好等于它两边
两个数的和，这一行最左边的几个数是这样的：0、1、3、8、21、……，问这一行最右边的一个数被6除的余数是多少？解：如果将这70个
数都写出来，再用6去除最右边的数，当然可以，但工作量比较大。本题中没有要求算出最右边的数，仅要求算出这个数被6除的余数。根据7
0个数组成的规律：中间一个数的三倍是它两边数的和。（除两头的两个数）那么中间这个数被6除的余数的3倍与两边两数被6除的余数之和再
被6除的余数应该相同（即在模6下同余）。将0、1、3、8、21、55、……被6除的余数依次写出来为0、1、3、2、3、1、……，
仔细观察这串余数，中间数的三倍与两边两数之和在模6下同余（被6除的余数相同）。因此用70个数中每个数被6除的余数组成的新数串来
代替原数串，不会影响题目的要求。这样工作量小多了。写新数串的工作量小了。让我们再来观察新数串是否有一定的规律。将新数串多些几个
数看看：0、1、3、2、3、1、0、5、3、4、3、5、0、1、3、2、3，……。可以看出前12个数作一段，将出现重复。70个
数的前5段共60个数，第六段的第10个数是4，这就是原来数串中第70个数被6除的余数。例3．求被7除的余数。解：由于这个数字太大
，真正除工作量太大，不过可以试一下是否有规律。试着除一下，发现111111可以被7整除，这样可以将被除数从高位开始六位一段
分割一下。2015=335×6+5，于是最后一段有5个1，11111÷7=1587……2，所以被7除余2.例4．求被6除的
余数。解：与上题比较，我们可以尝试用竖式除一下看看规律。85我们发现：除第一个1以外，每三位一段，1111被6除余1。这个1与
后面的三个1又组成1111。被6除还是余1。4831301又2014=3×671+1，所以原数除到最后是剩下11，11÷
6=1……5。所以被6除的余数为5.三．弃九法在进行计算时，要求准确无误。可是当数字较大或运算复杂时，容易出现错误。这就要求
我们有较简便的办法判断是否出错，如能迅速认定计算有误，将便于改正。如：算得4278×39682=169759894，这个式子一看
就知道不正确，因为末位数字8与2相乘，末位数字不可能是4。这种办法称为末位检验法。但如果计算得到4278×39682=16975
9896。从末位看不出问题，不敢确定计算有无错误。在“同余的几条简单性质”的例题中，我们曾计算三个数的乘积437×309×19
93被7除的余数，若改为计算437×309×1993被9除的余数，根据同余的性质可以分别计算437、309、1993被9除的余数
，再求余数之积被9除的余数。437≡(4+3+7)(mod9)≡5(mod9)；309≡(3+0+9)(mod9)≡3(
mod9)；1993≡(1+9+9+3)(mod9)≡4(mod9)。437×309×1993≡5×3×4(mod9)
≡60(mod9)≡6(mod9)。所以437×309×1993被9除余数是6.由于被9除的余数，只需计算数字和被9除的
余数，因而可以用被9除的余数来检验计算的错误情况。如计算得4278×39682=169759896，用末位检验看不出问题，若计
算正确，那么两端被9除的余数也应该相等。若两端被9除的余数不同，则一定是计算出了问题。由4278≡(4+2+7+8)(mod
9)≡3(mod9)；39682≡(3+9+6+8+2)(mod9)≡1(mod9)，所以左边被9除的余数是3。
而右边169759896≡(1+6+9+7+5+9+8+9+6)(mod9)≡6。所以计算一定有问题。以上方法称为弃九
法。不过应该注意，用弃九法可以发现问题，但是如果弃九法没有找出错误却不能保证计算一定正确。如果是除法，可以转化为乘法来检验。例5
．用弃九法检验465187586÷9762=47653是否可能正确。解：转化为检验乘法9762×47653=465187586。
9762≡(9+7+6+2)(mod9)≡6(mod9)，47653≡(4+7+6+5+3)(mod9)≡7(mod
9)，所以9762×47653≡6×7(mod9)≡42(mod9)≡6(mod9)，465187586≡(4+6+5
+1+8+7+5+8+6)(mod9)≡5(mod9)，所以9762×47653≠465187586，465187
586÷9762≠47653。练习题61．16×941×1611被7除所得的余数是。解：16≡2(mod7)，941≡3(
mod7)，1611≡1(mod7)，所以16×941×1611≡2×3×1(mod7)≡6(mod7)。所
得的余数是6.12．被41除所得的余数是。解：试除得11111÷41=271，对于，2016÷5=403……1从最高位开
始，每5个1分一段，可以得到403段，最后剩余1个1，这就是所得的余数。3．用弃九法检验乘法5483×9117=4988851
1是否可能正确。解：5483≡(5+4+8+3)(mod9)≡2(mod9)，9117≡0(mod9)，所以5483×9
117≡0(mod9)，49888511≡(4+9+8+8+8+5+1+1)≡8(mod9)，用弃九法知道计算不正确。4．
用弃九法检验除法1226452÷2683=334是否可能正确。解：2683≡(2+6+8+3)(mod9)≡1(mod9)，
334≡1(mod9)，而1226452≡(1+2+2+6+4+5+2)(mod9)≡4(mod9)，用弃九法知道
计算不正确。5．乘法算式3145×92653=291093995的横线处漏写了一个数字，那么横线处应填写。解：3145≡4(m
od9)，92653≡7(mod9)，所以3145×92653≡1(mod9)，设291093995的横线处填写的是a
，即2910a93995≡(2+9+1+0+a+9+3+9+9+5)(mod9)≡a+2(mod9)，所以a=8.86
．13511、13903、14589被自然数m除所得的余数相同，则m的最大值是。解：13903–13511=392，14589–
13903=686，用辗转相除法求392和686的最大公约数。686=1×392+294，392=1×294+98，29
4=3×98，所以392与686的最大公约数是98。即m的值是98.987．123123+456456+789789被3除的
余数是；被9除的余数是。00解：123≡0(mod3)，456≡0(mod3)，789≡0(mod3)，所以12312
3+456456+789789能被3整除，余数为0，123≡6(mod9)，62=36≡0(mod9)，所以123123≡
0(mod9)，456≡6(mod9)，所以456456≡0(mod9)，789≡6(mod9)，所以789789≡0
(mod9)，所以123123+456456+789789被9除的余数为0.8．将奇数按下列图排好，各列分别用A、B、C、D、
E、F、G作为代表，则2015所在的列以字母作为代表？AABCDEFG13579112321191715132527293133
35474543413937495153555759………………解：每行有6个奇数，从1开始数，到2015是第1008个奇数，
1008=6×168，所以2015在第168行上，按照规律，双数行的排列是从F到A的顺序排列，所以2015排在字母A所在的列。
9．证明：如果2和3均不能整除a和b，那么必有a2≡b2(mod24)。证明：由题意，2和3均不能整除a和b，即a，b都是奇数
，且不能被3整除，那么它们被3除的余数为1或2，即a≡1(mod3)，或a≡2(mod3)，若a≡1(mod3)，则a
2≡1(mod3)；若a≡2(mod3)，则a2≡1(mod3)，即对于符合题意条件的a，b一定都满足a2≡1(mod
3)，b2≡1(mod3)，所以a2–b2≡0(mod3)。即a2–b2能被3整除。再看a，b被8除的余数，由题意知a≡
1(mod8)或a=5(mod8)或a=7(mod8)，对于a≡1(mod8)，则a2≡1(mod8)；对于a≡5(
mod8)，则a2≡25(mod8)≡1(mod8)；对于a≡7(mod8)，则a2≡49(mod8)≡1(mod8
)；所以a2–b2≡0(mod8)。即a2–b2能被8整除。3和8互质，所以即a2–b2能被3×8=24整除。即a2≡b2
(mod24)。10．证明：形如8k+7的数不能表示为三个平方数的和。证明：对于所有的偶数，可以表示为2n(n为整数)的形式，
(2n)2=4n2，n2≡0(mod2)或n2≡1(mod2)，所以(2n)2≡0(mod8)或(2n)2=4(mod8
)，对于所有的奇数，可以表示为2m+1(m为整数)的形式，(2m+1)2=4m2+4m+1=4m(m+1)+1，其中m(m+1)一定可以被2整除，所以(2m+1)2≡1(mod8).由题意知8k+7≡7(mod8)，如果三个数都是偶数，则它们的平方和被8除的余数可能是0+0+0=0、0+0+4=4(mod8)、0+4+4≡0(mod8)、4+4+4≡4(mod8)，都不可能是7.如果是两个偶数一个奇数，则它们的平方和被8除的余数可能是0+0+1=1、0+4+1=5、4+4+1≡1(mod8)，也不可能是7。如果是一个偶数两个奇数，则它们的平方和被8除的余数可能是0+1+1=2或4+1+1=6，不可能是7.如果三个数都是奇数，则它们的平方和被8除的余数是1+1+1=3，也不是7.综上所述，形如8k+7的数不能表示为三个平方数的和。下课了！ |
|
