第三讲 同余（1）1

　　前面已介绍过整除的概念和带余除法

　　被除数=除数×商数+余数

　　在上面的式子里，若余数不为零，商叫做不完全商。

　　在生活中，人们也经常关心“余数”，让我们先看一个问题：

　　1993年6月1日是星期二，问20年后的6月1日是星期几？

　　由于每年有365天，20年有20×365=7300天，但每四年有一个闰年，20年中有5个闰年，故20年有7305天。

　　7305=7×1043+4

　　说明20年中有1043周，外加4天，我们关心的其实不是20年中有多少周，而是“外加的4天”（换句话说，关心的不是商数而是余数，有了余数就可求得20年后的6月1日是星期几）。因此，20年后的6月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

　　知37确实是所求的奇数。

　　换一下角度考虑：由于288和510被同一奇数除所得的余数相同，那么510和288差就一定是这个奇数的倍数。（求差时，相同的余数被减掉了）

　　∵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的自然数m所得的余数相同，就称a和b对于模m同余或a和b在模m下同余，记为

　　a≡b（modm）

　　有时也可简读作a与b同余，这时只是未将模m读出而已，很明显一谈到同余总与模有关容易看到，所有的偶数在模2下彼此同余，所有的奇数在模2下也彼此同余。

　　这里实际上是用2来将整数分成两类，一类被2整除（余数为零），另一类被2除余1。

　　偶数0，2，4，6，8，……，2k，……

　　奇数1，3，5，7，9，……，2k+1，……

　　如果用4来将整数分类，由于余数可为0、1、2、3共四种，因而可分为四类：

　　0，4，8，12，16……

　　1，5，9，13，17……

　　2，6，10，14，18……

　　3，7，11，15，19……

　　同一行的两个数，被4除的余数相同，也就是说在模4下同余，

　　如8≡16（mod4）5≡17（mod4）

　　2≡14（mod4）7≡15（mod4）

　　人们将一年的365天按星期日，星期一，星期二……星期六分为七类。

　　因此，对于每月的1号，8号，15号，22号，28号来说，1号是星期几，共其它几天也是星期几。

　　我们说过可用模将全体整数分类。

　　被3除余1的所有数，可用1（mod3）表示，即1，4，7，10……这些数的全体，这些数在模6下却分属两类，因为在模6下所有整数被分为下列六类：

　　0，6，12，18，……0（mod6）

　　1，7，13，19，……1（mod6）

　　2，8，14，20，……2（mod6）

　　3，9，5，21，……3（mod6）

　　4，10，16，22，……4（mod6）

　　5，11，17，23，……5（mod6）

　　1（mod3）表示1（mod6）和4（mod6）两类

　　被2除余1的数1（mod2），在模6下却分属三类，即1（mod6），3（mod6），5（mod6）

性质1任何整数都和自己同余，（这条性质称为自反性）a≡a（modn）。

性质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）

　　a-c≡b-d（modm）

　　a×c≡b×d（modm）

　　特别是当a≡b（modm），c=d对，有

　　a+c≡b+c（modm）

　　a-c≡b-c（modm）

　　ac≡bc（modm）

性质5甲和乙同余，那么甲和乙同次乘方的结果仍然同余。（这条称为可乘方性，实际上是可乘性反复运用的结果）

　　若a≡b（modm），n为自然数

　　以上各条性质和等式的性质十分相似，不过同余式终究不是等式，并不是等式的各种性质都能移到同余式中来使用。

　　注意，同余式中不能随意使用“可除性”。即在同余式ac≡be（modm）两端，如同除以c之后可能不同余。

　　如10≡6（mod4）

　　即5×2≡3×2（mod4）

　　但53（mod4）

　　又如16≡2（mod7）

　　即8×2≡1×2（mod7）

　　却有8≡1（mod4）

　　可见在ac≡be（mod4）两端同除以C后，可能有a≡b（modm）也可能ab（modm），这取决于c与m之间的关系。

　　结论是：如果（c，m）=1，有a≡b（modm），如（c，m）≠1，就可能有ab（modm）

例1求437×309×1993被7除的余数

　　分析：如将437×309×1993算出后，再用7去除从而求得余数，这显然是可以的，但是数字较大，比较麻烦，（实际上437×309×1993=269120769，被7除的余数为1）。

　　可将437，309，1993分别被7除求出余数，再用同余式性质将余数相乘即可容易得出原数被7除的余数。

解：∵437≡3（mod7）

　　 309≡1（mod7）

　　1993≡5（mod7）

　　利用同余式的可乘性，将三式相乘得

　　437×309×1993≡3×1×5（mod7）

　　≡15（mod7）≡1（mod7）

　　即437×309×1993被7除余1

例2 70个数排成一行，除了两头的两个数以外，每个数的三倍恰好等于它两边两个数的和，这一行数最左边的几个数是这样的：0，1，3，8，21……，问这一行数最右边的一个数被6除的余数是几？

分析 如果将这70个数都写出，再用6去除最右边的数当然可以，但工作量相当大。

　　本题中并未要求算出最右边的那个数，仅要求这个数被6除的余数。

　　根据这70个数组成的规律：中间的一个数的3倍是它两边的数的和。（两头的两个数除外）

　　那么中间那个数被6除的余数的3倍与两边两数被6除的余数之和再被6除的余数应该相同，（在模6下同余）

　　将0，1，3，8，21，55……，被6除的余数依次写出为0，1，3，2，3，1，……

　　仔细观察这串余数，中间的数的3倍与两边二数之和在模6下同余（被6除的余数相同）。因此，用70个数中每个数被6除的余数组成的新数串来代替原数串，不会影响题目的要求（求最右边的数被6除的余数）。现在变为求新的数串中最右的数了。

　　写新数串的工作量比原来小多了。让我们观察新数串是否有一定规律，如能找到规律还可进一步减少工作量。

　　将新数串（被6除的余数串）多写几个数试试看：

　　0，1，3，2，3，1，0，5，3，4，3，5，0，1，3，2，3，……

　　可以看出前12个数一段，将重复出现。

　　70个数的前5段共60个数，第六段的第十个数为4，这就是原来数串中第70个数被6除的余数。

例3 求被7除的余数

分析：由于这个数字太大，真正除工作量太大，不过可以试一试是否有某种规律。

　　经过试除发现111111可被7整除，这样可将被除数从最高位开始六位一段，由于共有1993个1，即有1993位。

　　1993=6×332+1

　　最后剩下的一位上的1，恰好是原数被7除的余数。

　　故被7除余数为1

　　（商为158730158730……158730。由332个158730连写组成）

　　如知道1001是7的倍数，那么

　　111111=100100+10010+1001

　　右端的3个数均为7的倍数，所以111111也是7的倍数。

　　再象上面那样，将从左往右六位一段，最后剩下1，被7除仍余1。

　　如将除数7改为6， 被6除的余数是多少？

　　作除法试试看

　　即除第一个1外每3位一段，1111111被6除余1，

　　1993-1=3×664

　　在商式上将出现185连写664次，在商中最后一个5的位置所对的1恰好为余数，因此

被6除余1。

　　改换一种考虑办法，由于6=2×3，可知原数数字和是1993个1之和为1993，而1993被3除余1。

　　即被3整除，而也被2整除，因此被6整除。

　　=+1

　　故被6除余1。

　　在进行计算时，要求准确无误，可是当数字较大或运算复杂时，容易出现错误，这就要求我们有较简便的办法判断是否出错，如能迅速认定计算有误将便于改正。

　　如4278×39682=169759894这个式子一看便知不正确，因为从末位数字8与2相乘，末位不可能是4，这种办法称为末位检验法。

　　但如改为4278×39682=169759896，从末位看不出问题，不敢确定计算有无错误。

　　在“同余的几条简单性质”的例1中，我们曾计算三个数的乘积被7除的余数，若改为计算乘积437×309×1993被9除的余数，根据同余的性质可分别计算437、309、1993，再求三个余数之积被9除的数即可

　　∵437≡（4+3+7）（mod9）≡5（mod9）

　　 309≡（3+9+0+）（mod9）≡3（mod9）

　　1993≡（1+9+9+3）（mod9）≡4（mod9）

　　∴437×309×1993≡5×3×4（mod9）

　　 ≡6（mod9）

　　故知437×309×1993被9除余6

　　由于求被9除的余数，只需计算数字和被9除的余数，因而可用被9除的余数来检验计算的错误。

　　如4278×39682=169759896，从末位看不出问题，若计算是正确的，那么两端被9除的余数应相同。若两端被9除余数不同，那么计算肯定有错。

　　由 4278≡3（mod9）

　　39682≡1（mod9）

　　有 4278×39682≡3（mod9）

　　但 169759896≡6（mod9）

　　∴4278×39682≠169759896

　　以上办法称为弃九法。不过应该注意，用弃九法可发现错误，但用弃九法没找出错误却不能保证原题一定正确。

　　如下列算式明显有错误，但用弃九法却未能发现。

　　1278×17384=216387

　　∵ 1278≡0（mod9）

　　17384≡5（mod9）

　　1278×17384≡0×5≡0（mod9）

　　而 216387≡0（mod9）

　　但从末位可见1278×17384≠216387，这就是说弃九法未发现问题，不能认为计算一定正确，（其实一个四位数乘以一个五位数不可能得到一个六位数）

　　对于除法算式转化为乘法即可检验。

　　如 465187586÷9762=47653是否正确？可转化为9762×47653=46518786是否正确？

　　从末位数字看，找不出问题。从被乘数的位数（四位），乘数的位数（五位）、积的位数（九位）看也找不出问题。

　　弃九法检查

　　9762≡6（mod9）

　　47653≡7（mod9）

　　9762×47653≡6×7≡42≡6（mod9）

　　但 465187586≡5（mod9）

　　∴ 9762×47653≠465187586

　　故 465187586÷9762≠47653

　　弃九法一般都用在整数范围内，对于小数运算可将小数先“当作”整数，方可使用弃九法。

　　如 0.12345×0.9876=0.12191820是否正确？只需看12345×9876=12191820是否正确，即直接去掉小数点，检查数字计算是否正确，再考察小数点位置是否正确。

　　1.求16×941×1611被7除的余数。

　　*2.求被41除所得的余数

　　3.用弃九法检验乘积

　　5483×9117=49888511

　　是否可能正确。

　　4.用弃九法检验商

　　1226452÷2683=334

　　是否可能正确。

　　5.乘法算式

　　3145×92653=2910____93995

　　的横线处漏写了一个数字，你能以最快的办法补出吗？

　　6.13511，13903，14589被自然数m除所得数相同，问m最大值是多少？

　　8.将奇数按下列图排好，各列分别用A、B、C、D、E、F、G作为代表，问1993所在的列以哪个字母作为代表？

　　A B C D E F G

　　1 3 5 7 9 11

　　23 21 19 17 15 13

　　25 27 29 31 33 35

　　47 45 43 41 39 37

　　49 51 53 55 57 59

　　……………………

　　*10.形如8k+7的数不能表为三个平方数的和。