中国剩余定理

显示全部楼层 · 2013-8-26 23:13:40

一个自然数除以7余4，除以8余3，除以11余1，求符合条件的最大三位数解：下面利用类似牛顿插值法的思路来解题。中国剩余定理则是类似拉格朗日插值。他们当然也可以统一。令这个数为x=4+7a+7*8b + 7*8*11 *~（这里~表示任意整数)亦即 x=4+7a+7*8b mod 7*8*11于是4+7a==3 mod 8，故取a==1 mod 8，不妨取a=1于是x==11+56 b又x ==1mod 11，故b==1 mod 11, 不防取b=1于是x==67 + 7*8*11* ~ 又要求 x为<1000的最大整数，故取x= 67+7*8*11 =67+616 = 683...

千问 · 2013-8-26 23:13:40

7×8=56=11×5+17×11×5=385=8×48+18×11×2=176=7×25+1于是此数可以为175×4+385×3+56=19157，8，11的最小公倍数为6161915÷616=3余67于是67为所求...