神马文学网第三讲 同余（一）
来源：百度文库 编辑：神马文学网 时间：2024/04/29 15:47:27
前面已介绍过整除的概念和带余除法
被除数=除数×商数+余数
在上面的式子里，若余数不为零，商叫做不完全商。
在生活中，人们也经常关心“余数”，让我们先看一个问题：
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为自然数
则am≡bm（modm）
以上各条性质和等式的性质十分相似，不过同余式终究不是等式，并不是等式的各种性质都能移到同余式中来使用。
注意，同余式中不能随意使用“可除性”。即在同余式ac≡be（modm）两端，如同除以c之后可能不同余。
如10≡6（mod4）
即5×2≡3×2（mod4）
但5
3（mod4）
又如16≡2（mod7）
即8×2≡1×2（mod7）
却有8≡1（mod4）
可见在ac≡be（mod4）两端同除以C后，可能有a≡b（modm）也可能a
b（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最大值是多少？
7.求123123+456456+789789被3和9除的余数
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
……………………
*9.如果2与3均不能整除a与b，那么必有a2=b2（mod24）
*10.形如8k+7的数不能表为三个平方数的和。
被除数=除数×商数+余数
在上面的式子里，若余数不为零，商叫做不完全商。
在生活中，人们也经常关心“余数”，让我们先看一个问题：
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为自然数
则am≡bm（modm）
以上各条性质和等式的性质十分相似，不过同余式终究不是等式，并不是等式的各种性质都能移到同余式中来使用。
注意，同余式中不能随意使用“可除性”。即在同余式ac≡be（modm）两端，如同除以c之后可能不同余。
如10≡6（mod4）
即5×2≡3×2（mod4）
但5
3（mod4）又如16≡2（mod7）
即8×2≡1×2（mod7）
却有8≡1（mod4）
可见在ac≡be（mod4）两端同除以C后，可能有a≡b（modm）也可能a
b（modm），这取决于c与m之间的关系。结论是：如果（c，m）=1，有a≡b（modm），如（c，m）≠1，就可能有a
b（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最大值是多少？
7.求123123+456456+789789被3和9除的余数
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
……………………
*9.如果2与3均不能整除a与b，那么必有a2=b2（mod24）
*10.形如8k+7的数不能表为三个平方数的和。