余数定理(一)可加性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,求这个数.此问题亦称“孙子问题”,有很多有趣的别名,如“韩信点兵”,“秦王暗点兵”,“鬼谷算”,“隔墙算”,“大衍求一术”等等.我国明朝有位大数学家叫程大位,他在解答“物不知其数”问题(即:有物不知其数,三三数之剩二,五五数之剩三,七七数之剩二,问物几何?)时用四句诗概括出这类问题的优秀解法:“三人同行七十稀,五树梅花廿一枝,七子团圆正月半,除百零五便得知.”这首诗就是解答此类问题的金钥匙,它被世界各国称为“中国剩余定理”(ChineseRemainderTheorem),是我国古代数学的一项辉煌成果.诗中的每一句话都表示一个步骤:三人同行七十稀,是说除以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的数,这个数可能是解答,但不一定是最小的,因此还要减去它们的公倍数.