同余定理总结

【例1】 （北大附中入学测试题）有一个自然数，用它分别去除63，90，130都有余数，这三个余数的和是25。这三个余数中最大的一个是多少？

答：63%kx + 90%kx + 130%kx = 25

(63+90+130)%kx = 25  283%kx=25

kx = 283-25 = 258

258 = 2*3*43

组和起来就是 2 3 43 6 86 129 258

2 3 6明显不满足 ，86 129 256 都大于 66

所以只可能是43

所以最大余数是20

（题外话：之所以会产生258不是直接的43 是因为，63+90+130除以kx最后余数为25，kx的不确定造成的。但这个数一定为 258的因数。而6因为使258的因子而在这里打了酱油。所以最后推出为43，最大余数为20）

【例2】 （人大附中入学测试题）一个两位数被它的各位数字之和去除，问余数最大是多少？

答：15

显然要使余数最大，余数就是除数 - 1，也就是说：

原两位数 + 1 要能被各位数字之和整除。并使此各位数字之和最大。

设两位数AB，则有：

(10A + B + 1) % (A + B) = 0

= (A + B + 9A + 1)% (A + B)

= 0 + (9A + 1) % (A + B)

要使各位数字之和最大：

当B = 9时，(9A + 1) % (A + 9) 是整数。

(9A + 1) % (A + 9) = (9A + 81 - 80)%(A + 9) = 0 – 80% (A + 9) 80% (A + 9)=0

80的因数有80、40、20、16、10、8……等。使A为个位数，A + 9是80因数的A最大是7。

这个两位数为79

79 ÷ ( 7 + 9) = 4 …… 15

余数定理：

a：两数的和除以m的余数等于这两个数分别除以m的余数和。

实例：7÷3=…1，5÷3=…2，这样（7+5）÷3的余数就等于1+2=3，所以余0。

b: 两数的差除以m的余数等于这两个数分别除以m的余数差。

实例：8÷3=…2，4÷3=…1，这样（8-4）÷3的余数就等于2-1=1，所以余1。

如果是（7-5）÷3呢? 会出什么问题？

c: 两数的积除以m的余数等于这两个数分别除以m的余数积。

实例：7÷3=…1，5÷3=…2，这样（7×5）÷3的余数就等于1×2=2，所以余2。

性质：

带余除法（也就是辗转相除法或者欧几里得算法）：

一般地，如果a是整数，b是整数（b≠0）,那么一定有另外两个整数q和r，0≤r＜b,使得a=b×q+r

当r=0时，我们称a能被b整除。

当r≠0时，我们称a不能被b整除，r为a除以b的余数，q为a除以b的不完全商（亦简称为商）。用带余数除式又可以表示为a÷b=q……r, 0≤r＜b

【例1】 一个大于10的自然数去除90、164后所得的两个余数的和等于这个自然数去除220后所得的余数，则这个自然数是多少？

答案：17

根据定理不解释

同余定义：

若两个整数a，b被自然数m除有相同的余数，那么称a，b对于模m同余，用式子表示为

a≡b(mod m) （*） 同余式（*）意味着（我们假设a≥b）a－b=mk，k是整数，即m|(a-b)

若两个数a，b除以同一个数c得到的余数相同，则a，b的差一定能被c整除

这条性质非常有用，一定要熟练掌握。下面是一些和同余有关的题目，这些题型都是考试经常出的，一定要掌握。

【例1】 一个大于10的数，除以3余1，除以5余2，除以11余7，问满足条件的最小自然数是多少？

答案：很显然是 172

(55a+66b+45c)%165

一般解题步骤:

①凑“多”相同，即把余数处理成相同 条件：余数与除数的和相同

②凑“缺”相同，即把余数处理成缺的数字相同 条件：除数与余数的差相同

③先考虑上面两种，如果都不行，则用“中国剩余定理”