首页 > 代码库 > 中国剩余定理的解释!

中国剩余定理的解释!

复习下中国剩余定理:

一个数n, 求满足n%3=2, n%5=3, n%7=2的最小数n.

先从3和5, 3和7, 5和7的最下公倍数中找出被7,5,3除余1的最小数,

分别是15,21,70。..

再分别用这三个数乘以对应的余数相加:

15*2+21*3+70*2=233

最后用233/105=2...23(余数)  (105为3,5,7的最小公倍数=3*5*7)

则:23为n

 

对于本题, 其实就是求满足

(n+d)%23=p

(n+d)%28=e

(n+d)%33=i

的最小的n的值.

由中国剩余定理可得:

n = (p*5544 + e*14421 + i*1288 -d +21252)%21252;  (数字自己算)