兩同余式組解的互補定理

王元恒

摘要：給出了兩個同余式組解間的互補定理，并說明應用此定理可以巧妙地“神奇化易”，利用一個同余式組的解來簡單求出另一個同余式組的解.

關鍵詞：同余式組解;孫子定理;互補關系

中圖分類號：O156.1 ? ? 文獻標志碼：A ? ? 文章編號：1674-9324（2016）42-0198-02

文[1]中給出了一次同余式的四種不同解法.其實，一次同余式在公元前二世紀時因天文歷法的需要而出現，同時也出現了同余式組

ax≡r（mod60）≡r（modb）

的求解問題（[2]），其中，a是一回歸年日數，b是一朔望月數.

《孫子算經》（成書于公元67—270年之間中）第26問題（[3]）：“今有物不知其數。三三數之剩二，五五數之剩三，七七數之剩二，問物幾何？答曰二十三.”原題后給出最小正整數解是23，并給出了具體的解法：三三數之剩二，置一百四十（70×2）;五五數之剩三，置六十三（21×3）;七七數之剩二，置三十（15×2）。并之得二百三十三，以二百一十減之即得。這種解法經后人整理發展即成為世界著名的孫子定理，或者稱為中國剩余定理，它比德國大數學家高斯（1777—1855）發表同樣的定理大約早1500年.

定理1（孫子定理）（[4]） 設m，…，m（k≥2）是兩兩互質的正整數，令M=m…m，M=M/m，M：MM≡1（modm），i=1，…，k.則一次同余式組x≡r（modm）≡…≡r（modm）的解為

x≡rMM+…+rMM（modM）.

由此可見，孫子問題求解中的70，21，15就是孫子定理中的MM，MM，MM.

數學問題的解決過程，是一個化未知為已知、化神奇為簡易的過程。與有物不知其數類似的問題，在小學數學奧賽中常出現，近年來在招聘公務員考試中也常出現.

例1（2007年山西省招考公務員試題） 幾百個糖，若平均分給7個小朋友，則多余3個，若平均分給8個小朋友，則多余6個，若再加3個，則可以平均分給5個小朋友，那么糖的數目可能有（ ?）種情況.

A.3種 ?B.4種 ?C.5種 ?D.6種

解1 此題屬于求一數，是其滿足：7除余3，8除余6，5除余2。由中國剩余定理可求出此數為：120×3+105×6+56×2-280k，當k取1，2，3時，其數小于1000，因此選A正確.

解2 生活中求解問題并不需要這么復雜，只需要計算出7，8，5的公倍數是7×8×5=280，然后用1000÷280的商3就是答案.

華羅庚先師教導我們（[5]）：“神奇化易是坦道，易化神奇不足提.”對于孫子問題，他說：“只要不是白癡，都能解得答案：分析問題中所給的條件，根據條件逐步尋求滿足條件的解（數），由三三數之剩二做起：把2記在心里，然后加3，于是有2+3=5，這時滿足第一個條件，再加3，即2+3+3=8，這時滿足第一個條件，同時也滿足第二個條件，現在就不必再加3，而是加[3，5]=15，立即可得8+15=23（為什么要加15，因為15為3，5的最小公倍數），23同時滿足問題中的三個條件，是滿足條件的最小正整數解.”孫子的神奇妙算問題，華羅庚僅用加法就求出了答案，印證了他老人家“神奇化易是坦道”的名言.或者更簡單，直接驗證7的倍數加2：2，9，16，23，…即得23為答案.但是，如果當同余式組的解很大時，就不好直接驗算時，還有什么另外簡單方法嗎？其實，本文發現有如下的“互補定理”，可以利用一個同余式組的解來簡單求出另一個同余式組的解.

定理2（互補定理） 設m，…，m（k≥2）是兩兩互質的正整數，令M=m…m，x為同余式組x≡b（modm）≡…≡b（modm）的解，y為同余式組y≡c（modm）≡…≡c（modm）的解.則

x+y≡0（modM）？圳b+c≡0（modm），i=1，…，k.

證明 由孫子定理知x≡∑bMM（modM），

y≡∑cMM（modM）.

所以，x+y≡∑（b+c）MM（modM）.

如果x+y≡0（modM），則x+y≡0（modm），i=1，…，k.又因為？坌j：1≤j≤k，當j≠i時有M≡0（modm），進而MM≡0（modm）;

當j=i時，MM≡1（modm）.故有

0≡x+y≡∑（b+c）MM≡b+c≡0（modm），i=1，…，k，即b+c≡0（modm）.

反之，如果b+c≡0（modm），則

0≡∑（b+c）MM≡x+y≡0（modm）.

j=1，…，k.又因為m，…，m（k≥2）兩兩互質，所以有x+y≡0（modm…m），即

x+y≡0（modM）.

證畢.

此定理好像是兩個同余式組間的一座橋梁，從而方便了直接驗證法求解.

例2 今有物不知其數。三三數之剩一，五五數之剩二，七七數之剩五，問物幾何？

解1 由孫子定理知，所求的解為

x≡1×70+2×21+5×15≡82（mod 105）.

解2 此問題正是孫子問題的互補問題，由于孫子問題的解是23，所以應用定理2得最小解為105-23=82.

例3（韓信點兵） 傳說的是西漢大將韓信剛拜將時，眾將官多有不服.一次他到校軍場，查點士兵人數.韓信讓士兵五五列隊余3人，七七列隊余2人，八八列隊余5人，九九列隊余2人，然后詢問人數.下級軍官故意把人數錯報為2395人，韓信聽后，哈哈大笑說：“不對。應當是2333人.”使下級將官們大吃一驚，從此對他十分敬佩.

解1 應用孫子定理（較繁的是計算），令

M=5×7×8×9=2520，M1=7×8×9=504，

M2=5×8×9=360，M3=5×7×9=315，

M4=5×7×8=280.

由MM≡1（modm），i=1，2，3，4，m=5，m=7，

m=8，m=9得到

M=4，M=5，M=3，M=1.

所以所求的解為

x≡3×504×4+2×360×5+5×315×3+2×280×1

≡2333（mod2520）

即韓信說的士兵人數應當是2333人.

解2 首先估計下士兵人數在2000人與2500人之間，而M=5×7×8×9=2520，所以應用定理2的互補方法，來考慮“韓信點兵”問題的互補問題.然后，再應用華羅庚先師的“神奇化易”的直接算法：

先在滿足第一條件的數列：

2，7，12，17，22，27，…

中找出同時滿足其他條件的數.例如同時滿足第一、三條件的數是27，而5和8的最小公倍數是40，所以又可在同時滿足第一、三條件的數列：

27，67，107，147，187，…

中找出同時滿足其他條件的數.數187就同時也滿足了第二條件，而5，7，8的最小公倍數是280，所以又可在同時滿足第一、二、三條件的數列：

187，187+280，187+2×280，…

中找出同時滿足第四條件的數，就是187.

于是應用定理2知道，士兵人數為2520-187=2333人.

顯然在具體計算求解時，解法2比較簡單，甚至小學生都會求解，我們大學數學師生更應該會求解.

最后應該指出的是，應用定理2（互補定理）在計算機上求解大型同余式組的解時，可以使計算工作量減少一半.

參考文獻：

[1]劉耀斌.一次同余式的解法探討[J].高等數學研究，2012，（4）：79-81.

[2]沈康身.中國剩余定理的歷史發展[J].杭州大學學報，1988，（3）：270-282.

[3]閔嗣鶴，嚴士健.初等數論[M].北京：高等教育出版社，1982.

[4]華羅庚.數論導引[M].北京：科學出版社，1958.

[5]華羅庚.從孫子的“神奇妙算”談起[M].北京：人民教育出版社，1964.

Complementary Theorem between the Solutions of Two Congruence Groups and Its Applications

WANG Yuan-heng

（Department of Mathematics，Zhejiang Normal University，Jinhua，Zhejiang 321004，China）

Abstract：The complementary theorem between the solutions of two congruence groups is given in this paper.So，one can get the solution of a congruence group from another solution of its complementary congruence group and some examples are given to show this.

Key words：solutions of congruence group;the Chinese remainder theorem;complementation