与孙子定理有异曲同工之妙的一个新的定理

wsc810

孙子定理中有如下问题* x=b1( mod m1) x=b2( mod m2) x=b3( mod m3) x=b4( mod m4) 求 x=b (mod m1m2m3m4) 现有如下新的定理，它可以将求解多个线性同余方程转化为求解一个同余方程的 一个类似于孙子定理的新的定理，它特别适合于计算机求解大型的线性同余方程组。 求解x ,则有 x = (b1*m2m3m4 + b2*m1m3m4 + b3*m1m2m4 + b4*m1m2m3)/(m2m3m4 + m1m3m4 +m1m2m49f+ + m1m2m3) ( mod m1m2m3m4 ) 例如，用它来解韩信点兵问题 x=1( mod 5) x=5( mod 6) x=4( mod 7) x=10( mod 11) 有 (1*462 + 5*385 + 4*330 + 10*210)/(462 + 385 + 330 + 210)=5807/1387=2111 (mod 2310)K.S 同样可以将 此定理 推广为 含有更多个同余方程组的解的显式表达式，大家也可以用其他的数来验证此定理的正确性 。

wsc810

更正 x = (b1*m2m3m4 + b2*m1m3m4 + b3*m1m2m4 + b4*m1m2m3)/(m2m3m4 + m1m3m4 +m1m2m4+ m1m2m3) ( mod m1m2m3m4 )

gxqcn

请注意： 1、如果发现自己的帖子出现“笔误”，12小时内可直接在原帖上修改； 2、本论坛发帖时已有多种主题类别可选，请不要再在标题中前冠以“[原创]”字样； 3、请不要动不动标榜：最新发现、重大发现。。。（如果真是这样，自有明白人会惊呼，比你自个来说更具说服力）

gxqcn

你的“定理”可经严谨证明？ 可否考虑过 m1、m2、... 彼此不全互素之情形？

winxos

原帖由 gxqcn 于 2009-4-28 19:02 发表 请注意： 1、如果发现自己的帖子出现“笔误”，12小时内可直接在原帖上修改； 2、本论坛发帖时已有多种主题类别可选，请不要再在标题中前冠以“[原创]”字样； 3、请不要动不动标榜：最新发现、重大发现。。。（如 ...

mathe

这本来就是孙子定理(或者说中国剩余定理)所解决的内容. 当然要求m1,m2,m3,m4互素(而对于不互素的情况,可以转化为互素的情况)

gxqcn

楼主描述的方法，其特点是模运算中仅有一次除法，也就是说仅用一次模逆过程。

gxqcn

当各个模彼此互素时，楼主的结论是成立的。 （当不互素时，可以简单的将某些模分解成两个或多个即可，即增加同余方程数） 但是否适合计算机求解，还有待讨论： 如果仅解这么一组同余方程组的话，楼主的算法是可以考虑的。 但如果当这些模数 $m_i$ 是常量，而针对不同的余数 $b_i$ 组合去计算 $x$， 此时直接用原始的孙子定理，虽然需要计算多组模逆，但这都是仅需一次的预运算， 所以整体效率会更高。

nyy

你这是“创造”了孙子定理，还是“重新发明”了孙子定理？

nyy

1. Clear["Global`*"];(*清除所有变量*)
   
2. rr={1,5,4,10}(*余数列表*)
   
3. mm={5,6,7,11}(*模列表*)
   
4. kkk=ChineseRemainder[rr,mm](*求解最小的非负整数解*)
   
5. mmm=LCM@@mm(*求最小公倍数*)
   

复制代码

求解结果
2111
2310