胡剑老师专题解析：不再复杂的余数（一）

   数论中除了整除以外，还有一个很重要也很难的知识点，就是余数，理解余数性质时，要与整除性联系起来，从被除数中减掉余数，那么所得到的差就能够被除数整除了．在一些题目中因为余数的存在，不便于我们计算，去掉余数，回到我们比较熟悉的整除性问题，那么问题就会变得简单了，这样就需要用到余数中一个非常重要的定理—同余定理。

   同余定义
   如果a，b除以c的余数相同，就称a，b对于除数c来说是同余的，且有a与b的差能被c整除．（a，b，c均为自然数）
   例如：17与13除以3的余数都是2，所以(17－11)能被3整除．

   同余定理
  （一）可加性
   a与b的和除以c的余数，等于a，b分别除以c的余数之和（或这个和除以c的余数）．
例如：23，16除以5的余数分别是3和1，所以(23+16)除以5的余数等于3+1=4．
注意：当余数之和大于除数时，所求余数等于余数之和再除以c的余数．
例如：23，19除以5的余数分别是3和4，所以(23+19)除以5的余数等于(3+4)除以5的余数。
  （二）可减性
a与b的差除以c的余数，等于a，b分别除以c的余数之差．
例如：23，16除以5的余数分别是3和1，所以(23－16)除以5的余数等于3－1=2．
注意：当较大数的余数小于较小数的余数时，所求余数等于c减去余数之差．
例如：23，19除以5的余数分别是3和4，所以 除以(23－19)的余数等于5－(4－3)=4.
  （三）可乘性
a与b的乘积除以c的余数，等于a，b分别除以c的余数之积（或这个积除以c的余数）．
例如：23，16除以5的余数分别是3和1，所以 除以5的余数等于 ．  
注意：当余数之积大于除数时，所求余数等于余数之积再除以c的余数．
例如：23，19除以5的余数分别是3和4，所以 除以5的余数等于 除以5的余数．
  （四）乘方性
如果a与b除以m的余数相同，那么an与bn除以m的余数也相同．

余数判别法
   当一个数不能被另一个数整除时，虽然可以用长除法去求得余数，但当被除位数较多时，计算是很麻烦的．建立余数判别法的基本思想是：为了求出“N被m除的余数”，我们希望找到一个较简单的数R，使得：N与R对于除数m同余．由于R是一个较简单的数，所以可以通过计算R被m除的余数来求得N被m除的余数．
⑴整数N被2或5除的余数等于N的个位数被2或5除的余数；
⑵整数N被4或25除的余数等于N的末两位数被4或25除的余数；
⑶整数N被8或125除的余数等于N的末三位数被8或125除的余数；
⑷整数N被3或9除的余数等于其各位数字之和被3或9除的余数；
⑸整数N被11除的余数等于N的奇数位数之和与偶数位数之和的差被11除的余数；
⑹整数N被7，11或13除的余数等于先将整数N从个位起从右往左每三位分一节，奇数节的数之和与偶数节的数之和的差被7，11或13除的余数就是原数被7，11或13除的余数

中国剩余定理：
  在一千多年前的《孙子算经》中，有这样一道算术题：“今有物不知其数，三三数之剩二，五五数之剩三，七七数之剩二，问物几何？”按照今天的话来说：一个数除以3余2，除以5余3，除以7余2，求这个数．此问题亦称“孙子问题”，有很多有趣的别名，如“韩信点兵”， “秦王暗点兵”，“鬼谷算”，“隔墙算”，“大衍求一术”等等．

   我国明朝有位大数学家叫程大位，他在解答“物不知其数”问题（即：有物不知其数，三三数之剩二，五五数之剩三，七七数之剩二，问物几何？）时用四句诗概括出这类问题的优秀解法：
“三人同行七十稀，五树梅花廿一枝，七子团圆正月半，除百零五便得知．”
这首诗就是解答此类问题的金钥匙，它被世界各国称为“中国剩余定理”（Chinese Remainder Theorem），是我国古代数学的一项辉煌成果．诗中的每一句话都表示一个步骤：
   三人同行七十稀，是说除以3所得的余数用70乘．
   五树梅花廿一枝，是说除以5所得的余数用21乘．
   七子团圆正月半，是说除以7所得的余数用15乘．
除百零五便得知，是说把上面乘得的3个积加起来，减去105的倍数，减得差就是所求的数．
   此题的中国剩余定理的解法是：用70乘3除所得的余数，21乘5除所得的余数，15乘7除所得的余数，把这3个结果加起来，如果它大于105，则减去105，所得的差如果仍比105大，则继续减去105，最后所得的整数就是所求．也就是2×70＋3×21＋2×15=233,233－105=128,128－105=23.
   为什么70，21，15，105有此神奇效用？70，21，15，105是从何而来？
先看70，21，15，105的性质：70被3除余1，被5，7整除，所以70a是一个被3除余a而被5与7整除的数；21是5除余1，被3与7整除的数，因此21是被5除余b，被3与7整除的数；同理15c是被7除余c，被3、5整除的数，105是3，5，7的最小公倍数．也就是说， 是被3除余a，被5除余b，被7除余c的数，这个数可能是解答，但不一定是最小的，因此还要减去它们的公倍数．