第五讲余数与同余
一、问题引入
上一讲我们已经学习了如何判断一个数能否被另一个数整除（主要总结除数为20以内整数的情况），这一讲中我们将会在此基础上，继续探讨如果一个数不能被另一个数整除，那么余数是多少，这是本讲将要讨论的第一个问题——余数问题。
我们知道，自然数（0和所有正整数），按能否被2整除可以分为偶数和奇数两类，即能被2整除（除以2余0）的数为偶数，不被2整除（除以2余1）的数为奇数，奇数和偶数各自有其特征，它们之间又有相互联系。
同理，如果我们以除以3的余数为标准，就可以将自然数分成三类，余0、余1、余2；如果我们以除以4的余数为标准，就可以将自然数分成四类，余0、余1、余2、余3；以除以n为标准，就可以将自然数划分为n类。
那么除以n余数相同的一类数有何共同的性质呢？除以n余数不同的数之间又有何联系呢？这是本讲将要讨论的第二个问题——同余问题。
二、知识总结
1、首先根据上一讲的整除特征，做简单推导，即可得到下列求余方法。
【注】下列方法大家以理解为主，不必死记。
着重掌握除以3、4、8、9、16的余数求法即可。
①求除以2的余数：奇数余1，偶数余0；
②求除以3的余数：等于该数的各位数字之和除以3的余数；
③求除以4的余数：等于该数末两位组成的数除以4的余数；
④求除以5的余数：等于该数个位数除以5的余数；
⑤求除以6的余数：该数的各个数字之和除以3得余数a，若该余数与原
数同奇同偶，则原数除以6的余数为a，若该余数与
原数一奇一偶，则原数除以6的余数为a+3；
⑥求除以7的余数：等于该数的末三位与末三位以前的数字组成的数之差
除以7的余数，如果数字仍然太大不能直接观察出来，
就重复此过程；
⑦求除以8的余数：等于该数的末三位除以8的余数；
⑧求除以9的余数：等于该数的各位数字之和除以9的余数；
⑨求除以10的余数：等于该数的个位数；
⑩求除以11的余数：（a）等于该数的奇数位上的数字之和与偶数的数字
之和的差除以11的余数
（b）等于该数的末三位与末三位之前的数字组成的
数之差除以11的余数，如果数字仍然太大不能直接
观察出来，就重复此过程；
⑪求除以13的余数：等于该数的末三位与末三位之前的数字组成的数之
差除以13的余数，如果数字仍然太大不能直接观察
出来，就重复此过程；
⑫求除以16的余数：等于该数的后四位除以16的余数;
⑬求除以17的余数：等于把该数的个位数字去掉，再从余下的数中，减
去个位数的5倍，所得到的数字除以17的余数，
如果数字仍然太大不能直接观察出来，就重复此过
程；
⑭求除以18的余数：该数的各个数字之和除以9得余数a，若该余数与原
数同奇同偶，则原数除以18的余数为a，若该余数
与原数一奇一偶，则原数除以18的余数为a+3；
⑮求除以19的余数：等于把该数的个位数字去掉，再从余下的数中，加
上个位数的2倍，所得数字除以19的余数。
如果
数字仍然太大不能直接观察出来，就重复此过程；
2、同余与同余的性质：
两个整数a，b，若它们除以整数m所得的余数相等，则称a，b对于模m同余。
一般记为a≡b（mod m）。
同余有以下常用的性质：
（1）如果a ≡b (mod m)，则a、b之差（大数减小数）能被m整除。
（2）传递性如果a ≡b (mod m)，b ≡c (mod m),那么a ≡c (mod m)；
（3）可加性
如果a ≡b (mod m)，那么
a +c ≡
b +
c (mo
d m)；
如果a ≡b (mod m)，c ≡d (mod m),那么
a ±c ≡
b ±d (mod m)；
（4）可乘性
如果a ≡b (mod m)，那么
a ×c ≡
b ×
c (mo
d m)；
如果a ≡b (mod m)，c ≡d (mod m),那么
a ×c ≡
b ×d (mod m)；
（5）乘方性
如果a ≡b (mod m)，那么
a n≡
b n (mod m)
掌握了同余的性质，可以拓展解题思路，也可以简化计算。
3、余数互补：
如果a除以m的余数为p，b除以m的余数为q，若p+q=m或0，则a与b除以m的余数互补。
余数互补在周期性游戏与策略问题中经常出现。
三、例题讲解
例1: 求余方法
求2008除以7及除以9的余数
【分析】
2008末三位为008，即8，末三位与之前数字的差为8-2=6，所以2008除以7 的余数为6。
2008各个位上的数字和为10，除以9的余数为1，所以2008除以9的余数为1。
例2：同余的性质
有一个整数，用它去除300、262、205，得到的余数相同.这个数是多少？
【分析】
设这个除数为m，根据同余的性质（1），300-262=38能够被m整除，262-205=57能够被m整除，300-205=95能够被m整除。
所以m为38、57、95的公约数，且不为1。
因此m=19。
例3：同余的性质
求437×309×1993被7除的余数
【分析】
437除以7余数为3，即473≡3（mod7）
309除以7余数为1，即309≡1（mod7）
1993除以7余数为5，即1993≡5（mod7）
由同余的性质（4）可知472×309×1993≡3×1×5（mod7）≡1（mod7）。
所以437×309×1993被7除的余数为1。
例4：除数不同的同余
一个数用3除余1，用5除余2，用7除余2，则满足条件的最小自然数是多少？
【分析】
设该数为m，则m-2为5和7的公倍数，且m-1=（m-2）+1为3的倍数。
5和7的公倍数为35、70、105、140……,其中这些数加1后位3的倍数的最小自然数为35，所以m为37。
例5：余数互补、取火柴问题
两人做取火柴的游戏：桌上有500根火柴，两人轮流取，每一次可以取走1,2,4,8……(2的任意次方)根火柴，谁先没火柴取谁输。
试问在正确的玩法之下，谁会取胜？是先取者还是后取者？
【分析】
这是道取火柴问题，是典型的周期性的游戏与策略问题，解题过程中要用到余数互补的思想。
每次取火柴可以取2的任意次方根，2的任意次方都不能被3整除，除以3的余数为1或2，而1与2互补。
设先取者为甲，后取者为乙。
甲可以取走两根火柴，使剩下的498根火柴是3的倍数，则乙不论如何取，只能取走2k根火柴，2k不是3的倍数，所以乙一定无法取走全部的火柴。
那么乙取完后剩下的火柴数除以3的余数为1或2，只要甲取走与乙取的火柴数余数互补的火柴数（即乙取的火柴数除以3余1则甲取的火柴数除以3余2，乙取的火柴数除以3余2则甲取的火柴数除以3余1），即可使剩下的火柴数仍是3的倍数而使下次乙仍无法取走所有的火柴，于是乙永远无法取胜，先取者会获胜。