中国剩余定理解法5个5数之余3,6个6数之余4,7个7个数之余1,问这个数是多少

中国剩余定理解法5个5数之余3,6个6数之余4,7个7个数之余1,问这个数是多少
中国剩余定理解法
5个5数之余3,6个6数之余4,7个7个数之余1,问这个数是多少

中国剩余定理解法5个5数之余3,6个6数之余4,7个7个数之余1,问这个数是多少
令m n t y为整数,设该数为x
x=5m+3=6n+4=7t+1
6n=5m-1 因此6n的尾数应该是4或9（其实9也可以排除,9不能被2整除）
将4 9 14 19.带入(应该很快想到24）
可得 n的最小值为4,算出满足5个5数之余3,6个6数之余4的最小数为28
又因为5和6的最小公倍数为30
则x=28+30y=7t+1
t=4+(30y-1)/7
因此只要让（30y-1)/7为整数即可
而30y-1尾数应该是9 所以（30y-1)/7的尾数应该是7,将7 17.带入
可得y=4,所以x=28+30*4=148（最小值）
再准确点x=148+210*z(z为整数,210是5 6 7最小公倍数）

5个5个数之余3,6个6个数之余4,7个7个数之余1，问这个数是多少
这个数为148+210k,k为整数。下面解出三种解法。
在解法二中，对中国剩余定理作了简易的表述，容易理解。事实上，中国剩余定理的方法，与拉格朗日插值法相似。解法一相当于牛顿插值。解法三中，用插值法来解这个题。
题目的等效说法:
一个数,除以5(以5除之)余3,除以6余4,除以7余1,求这个数.<...

全部展开

5个5个数之余3,6个6个数之余4,7个7个数之余1，问这个数是多少
这个数为148+210k,k为整数。下面解出三种解法。
在解法二中，对中国剩余定理作了简易的表述，容易理解。事实上，中国剩余定理的方法，与拉格朗日插值法相似。解法一相当于牛顿插值。解法三中，用插值法来解这个题。
题目的等效说法:
一个数,除以5(以5除之)余3,除以6余4,除以7余1,求这个数.
一个数,以5累减之余3,…，求这个数。
x==3 mod 5 ==4 mod 6 ==1 mod7,求x. (数论表述)
注:
5,6,7的最小公倍数[5,6,7]，或记成lcm(5,6,7)=5*6*7 (两两互质)
解法一:逐步修正(对中国剩余定理类似于牛顿插值一样改造)
(基于x==3 mod 5,)设x=3+5a+5*6b+5*6*7c.即x==3+5a+5*6b mod 5*6*7
由x==4 mod 6得 3+5a==4 mod 6,（5a==1==-a）,a==-1 mod 6,不妨取作a=-1;
代入即得x==-2+30b mod 210
由x==1 mod 7得 -2+30b==1 mod 7,（30b==3,-90b==-9==5==b mod 7,取b=5.
代入即得x==-2+150==148 mod 210.
这种方法的相比中国剩余定理，各有其好处。这里的好处是，减少了一个同余式的求解过程；但是余数的进行了逐步修正，又有了新的变化。
题目复制：
x==3 mod 5 ==4 mod 6 ==1 mod7,求x.
注：
5,6,7的最小公倍数[5,6,7]，或记成lcm(5,6,7)=5*6*7 (两两互质)
解法二：将中国剩余定理的转化为以下简易的表述
令x=3a*6*7+4b*5*7+1c*5*6
代入已知，易见a*42==1 mod 5,b*35 ==1 mod 6,c*30==1 mod 7
解得a*(-84)==-2==a mod 5,-35b==-1==b mod 6,-90c==-3==c mod 7
不妨取a=-2,b=-1,c=-3，代入上式求解。
但是这样实际上在实际的计算上不如用下面的办法。
令x=A*6*7+B*5*7+C*5*6 ($$$)
代入已知，易见A*42==3 MOD 5,B*35 ==4 MOD 6,C*30==1 MOD 7
解得A==-1 MOD 5,B==-4==2 MOD 6,-90C==-3==4==C MOD 7
不妨取A=-1,B=2,C=-3，代入$$$式求解得到：
x=-42+70+120=148
事实上，这个计算过程还可以简化。有兴趣，请见：
我的空间中相关的文章:
http://hi.baidu.com/wsktuuytyh/blog/item/3341153dd73cc9cb9e3d622d.html#comment
http://hi.baidu.com/wsktuuytyh/blog/item/3411f92d4df9bb38359bf74d.html
解法三：参见
http://hi.baidu.com/wsktuuytyh/blog/item/c5c77cecc66d6d302697918a.html

收起