王元恒

摘要：給出了兩個(gè)同余式組解間的互補(bǔ)定理，并說(shuō)明應(yīng)用此定理可以巧妙地“神奇化易”，利用一個(gè)同余式組的解來(lái)簡(jiǎn)單求出另一個(gè)同余式組的解.

關(guān)鍵詞：同余式組解;孫子定理;互補(bǔ)關(guān)系

中圖分類號(hào)：O156.1 ? ? 文獻(xiàn)標(biāo)志碼：A ? ? 文章編號(hào)：1674-9324（2016）42-0198-02

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

ax≡r（mod60）≡r（modb）

的求解問(wèn)題（[2]），其中，a是一回歸年日數(shù)，b是一朔望月數(shù).

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

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

x≡rMM+…+rMM（modM）.

由此可見(jiàn)，孫子問(wèn)題求解中的70，21，15就是孫子定理中的MM，MM，MM.

數(shù)學(xué)問(wèn)題的解決過(guò)程，是一個(gè)化未知為已知、化神奇為簡(jiǎn)易的過(guò)程。與有物不知其數(shù)類似的問(wèn)題，在小學(xué)數(shù)學(xué)奧賽中常出現(xiàn)，近年來(lái)在招聘公務(wù)員考試中也常出現(xiàn).

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

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

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

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

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

定理2（互補(bǔ)定理） 設(shè)m，…，m（k≥2）是兩兩互質(zhì)的正整數(shù)，令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.又因?yàn)?？坌j：1≤j≤k，當(dāng)j≠i時(shí)有M≡0（modm），進(jìn)而MM≡0（modm）;

當(dāng)j=i時(shí)，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.又因?yàn)閙，…，m（k≥2）兩兩互質(zhì)，所以有x+y≡0（modm…m），即

x+y≡0（modM）.

證畢.

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

例2 今有物不知其數(shù)。三三數(shù)之剩一，五五數(shù)之剩二，七七數(shù)之剩五，問(wèn)物幾何？

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

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

解2 此問(wèn)題正是孫子問(wèn)題的互補(bǔ)問(wèn)題，由于孫子問(wèn)題的解是23，所以應(yīng)用定理2得最小解為105-23=82.

例3（韓信點(diǎn)兵） 傳說(shuō)的是西漢大將韓信剛拜將時(shí)，眾將官多有不服.一次他到校軍場(chǎng)，查點(diǎn)士兵人數(shù).韓信讓士兵五五列隊(duì)余3人，七七列隊(duì)余2人，八八列隊(duì)余5人，九九列隊(duì)余2人，然后詢問(wèn)人數(shù).下級(jí)軍官故意把人數(shù)錯(cuò)報(bào)為2395人，韓信聽(tīng)后，哈哈大笑說(shuō)：“不對(duì)。應(yīng)當(dāng)是2333人.”使下級(jí)將官們大吃一驚，從此對(duì)他十分敬佩.

解1 應(yīng)用孫子定理（較繁的是計(jì)算），令

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）

即韓信說(shuō)的士兵人數(shù)應(yīng)當(dāng)是2333人.

解2 首先估計(jì)下士兵人數(shù)在2000人與2500人之間，而M=5×7×8×9=2520，所以應(yīng)用定理2的互補(bǔ)方法，來(lái)考慮“韓信點(diǎn)兵”問(wèn)題的互補(bǔ)問(wèn)題.然后，再應(yīng)用華羅庚先師的“神奇化易”的直接算法：

先在滿足第一條件的數(shù)列：

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

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

27，67，107，147，187，…

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

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

中找出同時(shí)滿足第四條件的數(shù)，就是187.

于是應(yīng)用定理2知道，士兵人數(shù)為2520-187=2333人.

顯然在具體計(jì)算求解時(shí)，解法2比較簡(jiǎn)單，甚至小學(xué)生都會(huì)求解，我們大學(xué)數(shù)學(xué)師生更應(yīng)該會(huì)求解.

最后應(yīng)該指出的是，應(yīng)用定理2（互補(bǔ)定理）在計(jì)算機(jī)上求解大型同余式組的解時(shí)，可以使計(jì)算工作量減少一半.

參考文獻(xiàn)：

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

[2]沈康身.中國(guó)剩余定理的歷史發(fā)展[J].杭州大學(xué)學(xué)報(bào)，1988，（3）：270-282.

[3]閔嗣鶴，嚴(yán)士健.初等數(shù)論[M].北京：高等教育出版社，1982.

[4]華羅庚.數(shù)論導(dǎo)引[M].北京：科學(xué)出版社，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