中国剩余定理的改进

-52-孙子定理的一点改进摘要：对孙子定理稍加改进，略去了定理的最后一步．从而减少了计算的工作量，特别是未知量多时，使位数大大降低．关键词：同余方程算法完全剩余系关于解联立同余方程组的问题，我国古代取得了辉煌的成果，这就是著名的中国剩余定理，又称孙子定理1,在孙子算经里曾提出并解决了下列的问题＂今有物不知其数，三三数之剩二，五五数之剩三，七七数之剩二，问物几何？＂其解法为＂三三数之剩二，置一百四十，五五数之剩三，置六十三，七七数之剩二，置三十，并得之得二百三十三，以二百十减之即得＂答案是＂有物二十三＂把这个问题的提法和解法用现在的说法来表达，它可以写成这样：解同余方程组：)7(mod2)5(mod3)3(mod2zyx这个具体问题得答案是)105(mod232333063140215321270x一般来说，若一数用3除余a,用5除余b,用7除余c,则此数是)105(mod152170cbax关于这个问题的一般解法，在明朝程大位的《算法归宗》里有一首歌，就是＂三人同行七十稀，五朵梅花二十一，七子团圆整半月，除百零五便得知＂究竟70,21,15是怎样得来得呢？这将从下列定理中看出：定理：若nmmmn,...,,,221是两两互质的正整数，令nnnMmMmMmmmmM......221121则nkmcxkk,...,2,1,.....,(mod）这n个同余式只有一个公共解．)(mod)(mod...222111McaMMcaMcaMcaMxnkkkknnn这就是著名的中国剩余定理，又称孙子定理[1][2][3],中国历代数学家曾经给这个定理内的各种数规定了一定的名称，笔者认为清朝黄宗宪的＂大衍求一术＂的规定最为全面，他是这样规定的：定母：nmmmn,...,,,221衍母：nmmm．，，，...21衍数：nmmmM...21-53-乘数：naaa．，，...21用数：nnaMaMaM，，．．．，，2211剩数；nccc，，．，...21各总：nnncaMcaMcaM，，．．，..222111所求率：)(mod)(mod...222111McaMMcaMcaMcaMnkkkknnn所求总：所求率被M除后的最小正余数．2,笔者在研究洛阳民间流传的拣桃问题中［4］，遇到了需要求十四个同余式组成的同余方程组。),43(mod33),....41(mod2),.37(mod4),...31(mod16),....29(mod24),..23(mod17),.19(mod11),....17(mod11),......13(mod4),....11(mod8),.....7(mod4),......5(mod4),.......3(mod2),......2(mod0xxxxxxxxxxxxxx这个问题的43.41.37.31.29.23.19.17.13.11.7.5.3.2M是一个十六位的数字，141kkkkcaM就更大了，这就迫使笔者考虑这一问题，孙子定理能否改进．3,笔者改进的算法如下：令：1112macx使)(mod222mcx再令21223mmaxx使)(mod333mcx依次类推，若已经求出1kx则令12111...kkkkmmmaxxx使其)(modkkmcx这里的Mmmmxxnk...21，这算法是递推的证明：用数学归纳法当t=1时111112mcmacx．．．又)(mod222mcx故...).........(................................0.......................)(121221212121211ccccmccccccccfma若若若又1),21mm（所以1211)1,...(2,,0mmmm是一个完全剩余系，从而21ma即121ma故211211112)1(mmmmmmacx假设时对于时有ktmmmxktkt121....1Mmmmmmmmmmmmmmmaxxkkkkkkkkk12112112112111......)1(...,...-54-以本文开头的题目为例，用我们改进的算法来解：令：82)5(mod13),5(mod33221112xaaax即得令1),7(mod1)7(mod827)7(mod8215),7(mod2538222aaax即231158x上面提到的实际问题用此法解得834,683,542473,386,9x再举一个例题：二数余一，五数余二，七数余三，九数余五，问本数？),9(mod5),7(mod3),5(mod2),2(mod1xxxx解：43767017,6,),9(mod5701717,1),7(mod31077,3),5(mod12),5(mod221334322321112xaaxxaaxxaaax参考文献：[1]华罗庚《数论导引》第一版，北京科学出版社195732--34[2]闵嗣鹤《初等数论》第二版北京人民教育出版社198261--63[3]陈景润《初等数论》第一版北京科学出版社197883--85[4]符文通马国祥从拣桃问题谈起《全国第五届MPMH会议文集》西南交通大学出版社1994334—339洛阳大学学报(自然科学版)1995年第二期…