用程序计算中国剩余定理

海里游

中国剩余定理的算法一直是古老的算法，有了计算机没有新的算法也不能进行复杂的运算，本人总结了一种新算法，用程序运行得到适合条件的最小数，与大家共享。
如果要求所有适合条件的数，用适合条件的最小数加上所有除数的最小公倍数

如果我要是简单的说
x=5mod11
x=9mod13
x=3mod17
x=13mod37
x=19mod31
x=17mod43
x=11mod123
得到最小适合条件的数是8914953173可能有作弊的嫌疑
那么我用123456789中的12、23、34、45、56、67、78作除数用2、3、4、5、6、7、8作余数，再找适合这样条件的最小数你还怀疑吗？
x=2mod12
x=3mod23
x=4mod34
x=5mod45
x=6mod56
x=7mod67
x=8mod78
得到最小适合条件的数是
11234797790
或者用123456789中的12、23、34、45、56、67、78作除数用1、2、3、4、5、6、7作余数
x=1mod12
x=2mod23
x=3mod34
x=4mod45
x=5mod56
x=6mod67
x=7mod78
得到最小适合条件的数是
11234797789
我也才发现，这个数与上面的数怎么差不多呢，这会让人怀疑是不是利用了数的什么规律得出来的，这个规律还真得值研究研究。
为了避嫌，用除数的数字之和做余数。
用12、23、34、45、56、67、78作除数用3、5、7、9、11、13、15作余数
x=3mod12
x=5mod23
x=7mod34
x=91mod45
x=11mod56
x=13mod67
x=15mod78
得到最小适合条件的数是
4447107459
不过大家不要误会，除数、余数不是随便编的，前提确实存在那么个数才行，也就是，有一个未知数只知道他分别被a1、a2、a3、……an除，余数分别为b1、b2、b3、……bn
通过这样的除数和余数才能求出适合条件的最小数，那个未知的数，也许是这个最小数，也许是最小数加上若干倍a1、a2、a3、……an的最小公倍数。如果随意取除数和对应的余数，不一定都有结果。

mathematica

用mathematica计算中国剩余定理

参看我的回复：
http://bbs.emath.ac.cn/redirect. ... o=lastpost#lastpost

海里游

编程高手不敢较量。
我的程序不是模运算是函数计算，对于我这低手来说也曾试过模运算，
相比之下函数计算要减少很多运行次数，不过对于你这高手来说，无所谓什么算法，
也都能很快实现，我在这里学习了。

mathematica

参见这边的回复
http://bbs.emath.ac.cn/redirect. ... o=lastpost#lastpost
我又增加内容了!!!!!!!!!!!!!!

海里游

佩服！
希望能确认一下：计算适合下面10和11个条件最小数的时间、
前面是除数，后面是对应的余数。
546357,59781
9689641,8356469
9767641,635730
8767641,2580909
8769781,1337652
8767671,7218570
8745679,2598568
9945679,6598568
19945679,9768568
39945679,10767568
得377015171641327388423314171573260603209660132334414913604279636958
再加一个条件：
546357,59781
9689641,8356469
9767641,635730
8767641,2580909
8769781,1337652
8767671,7218570
8745679,2598568
9945679,6598568
19945679,9768568
39945679,10767568
739945321,65107675

wayne

5# 海里游
1067843838077398806824856020630918695454468820379724531786363078872355932122

Mathematica 瞬间即可算出来的

mathematica

代码文件以及图片都在附件里面,你自己看看吧!
其实这些东西都不消耗什么计算时间的!

mathematica

代码文件内容:

\r chineseM.gp
a=[59781,8356469,635730,2580909,1337652,7218570,2598568,6598568,9768568,10767568]
b=[546357,9689641,9767641,8767641,8769781,8767671,8745679,9945679,19945679,39945679]
chineseM(a,b)
a=[59781,8356469,635730,2580909,1337652,7218570,2598568,6598568,9768568,10767568,65107675]
b=[546357,9689641,9767641,8767641,8769781,8767671,8745679,9945679,19945679,39945679,739945321]
chineseM(a,b)
很简单的!!!!!!!!!

mathematica

或者使用下面的代码,这样可以保存结果.
\r chineseM.gp
a=[59781,8356469,635730,2580909,1337652,7218570,2598568,6598568,9768568,10767568]
b=[546357,9689641,9767641,8767641,8769781,8767671,8745679,9945679,19945679,39945679]
chineseM(a,b)
\w
a=[59781,8356469,635730,2580909,1337652,7218570,2598568,6598568,9768568,10767568,65107675]
b=[546357,9689641,9767641,8767641,8769781,8767671,8745679,9945679,19945679,39945679,739945321]
chineseM(a,b)
\w

mathematica

结果是:
Mod(377015171641327388423314171573260603209660132334414913604279636958, 1588353008051967115688819881528670581870780595008940491749652793367)
Mod(1067843838077398806824856020630918695454468820379724531786363078872355932122, 1175294376404328392099807963348914124405631527894461470037594687826491485807)