孫子定理的Python簡單分析與應用

王薇　王德貴

孫子定理，是中國古代求解一次同余式組的方法，是數論中一個重要定理，又稱為中國剩余定理、中國余數定理，它也是數論四大定理（威爾遜定理、費馬小定理、孫子定理、歐拉定理）之一。

一元線性同余方程組問題最早見于中國南北朝時期（公元5世紀）的數學著作《孫子算經》卷下第二十六題，叫作“物不知數”問題，原文：

有物不知其數，三三數之剩二，五五數之剩三，七七數之剩二。問物幾何？即，一個整數除以三余二，除以五余三，除以七余二，求這個整數。《孫子算經》中首次提到了同余方程組問題，以及以上具體問題的解法，因此在中文數學文獻中也會將中國剩余定理稱為孫子定理。

用現代數學的語言來說明的話，孫子定理給出了以下的一元線性同余方程組：

，其中m、m…m兩兩互素。

整數x同余于a1模m1，即x%m1 = a1%m1，……

方程組一般用構造法求出x的最小整數解。由于求解方法中的理論比較難于理解，后面再做詳述。

對于整數，數學家們一直很熱衷于整除、因數、余數和素數等方面的研究，因而也出現了數論四大定理等很多相關的定理和猜想。在這四大定理之中，我們已經用Python驗證了費馬小定理和威爾遜定理，今天我們就利用Python由簡單入手，來求解孫子定理相關的問題。

設計思路是由淺入深，先研究兩個條件的簡單問題求解方法，然后在此基礎上，再討論多個條件的情況，最后討論孫子定理及應用。

程序設計涉及的是等級考試四級和二級內容。

（1）余同加余

一數除以3余1，除以4余1，求這數。

這個數減去1，即是3的倍數，也是4的倍數，那就是12的倍數，即x =12k +1，那么最小值為13。

（2）和同加和

一數除以3余2，除以4余1，求這數。

這個數減去2，是3的倍數，可能是2，5，8……，這個數減去1是4的倍數，可能是1，5，9……，余數為5時相同。則根據上一條件，可以將問題修改為除以3余5，除以4余5，則x =12k +5，最小值為17。同時我們發現模和余數的和相等，因此稱為和同加和。

（3）差同減差

一數除以3余1，除以4余2，求這數。

仿照上例，這個數減去1，是3的倍數，余數還可能是-2，-5，-8……，這個數減去2是4的倍數，-2，-6，-10……我們看到模與余數和差相同，所以x =12k -2，最小值為10。稱為差同減差。

（4）其他情況

一數除以3余1，除以4余3，求這數。

沒有上述3個題目的特點，非特殊情況，我們采用枚舉法。即在第一個條件下，x=3k+1，那么依次將k值加1，再求出x除以4的余數，如果余數為3，x即為所求。x值依次為4，7，10，13，16，19，22……那么7，19……均滿足條件，取最小值為7。

（5）程序設計

根據前面的分析，四種情況的程序如圖1。

測試結果如下，這是有兩個條件下的求解。顯示兩個列表元素，是為了我們分析方便（圖2）。

在兩個條件的基礎上，擴展到三個及三個以上的條件時，也可以用枚舉法，則需要解決以下問題。

（1）輸入數據：多組數據存儲在列表中，m存儲模，a存儲余數。因為輸出條件不定，所以用while循環，以回車結束輸入。

然后比較余數和模，如果余數大于模，重新輸入數據。

（2）判斷互素：多組模值，依次判斷是否兩兩互素。可以根據最大公約數來判斷。

（3）枚舉：通過枚舉滿足第一個條件的數，依次判斷是否滿足其他條件。當所有的條件都滿足，則終止循環，輸出x值。

根據以上分析，編寫程序如圖3。

驗證結果（圖4）。

韓信帶1500名兵士打仗，戰死四五百人，站3人一排，多出2人;站5人一排，多出3人;站7人一排，多出2人，還有士兵多少人？

這是一道經典的問題，前面已經求出滿足條件的最小值為23。因為士兵應該在1000多人左右，所以再加上3×5×7=105的倍數就可以了，所以加上1050，韓信的士兵人數為1073人。

如果采用枚舉法求解，根據題意，損失人數是400-500之間，因此剩余士兵人數應該在1000-1100人之間，結果是1073人。程序和測試結果如下（圖5）。

現在我們回到正題，利用孫子定理求解的方法。

（1）同余定理

最先引用同余的概念與符號者為德國數學家高斯。同余理論是初等數論的重要組成部分，是研究整數問題的重要工具之一。

兩個整數a、b，若它們除以大于1的正整數m所得的余數相等，則稱a與b對于模m同余或a同余于b模m。

記作：a≡b （mod m），

讀作：a同余于b模m，或讀作a與b對模m同余，例如26≡2（mod 12）。

顯然，有如下性質：

1）若a≡0（mod m），則m|a（m整除a，a被m整除）;

2）a≡b （mod m），則a-b≡0（mod m），a-b|m。

3）反身性：a≡a （mod m）;

4）對稱性：若a≡b（mod m），則b≡a （mod m）;

5）傳遞性：若a≡b（mod m），b≡c（mod m），則a≡c（mod m）;

6）同余式相加：若a≡b（mod m），c≡d（mod m），

則a±c≡b±d（mod m）;ac≡bd（mod m）。

（2）孫子定理內容

正整數m1、m2…mn兩兩互素，對a1、a2…an的同余方程組為：

（3）程序設計

為了方便大家理解，我們分步設計程序。

①最大公約數

為了判斷模的互素，自定義函數求最大公約數（圖6）。

②判斷互素（圖7）

遍歷列表m，通過自定義函數，判斷是否互素時調用最大公約數函數，如果為1，則為互素。

③求mi乘積M

遍歷列表m，求各項的積（圖8）。

④求Mi=M/mi存入列表Mi[ ]中（圖9）

⑤求Mi逆元（數論倒數）存儲在列表Mi_[ ]中

求逆元的方法，也是遍歷。當然也可以用庫方法，這里不再研究（圖10）。

⑥求Mi[i]Mi_[i]a[i]乘積的累加存入變量x，并計算結果（圖11）

⑦定義模和余數列表，并調用自定義函數，輸出結果（圖12）

⑧測試結果（圖13、圖14）

與前測試結果相同。

完整程序，如圖15。

三、測試與改進

孫子定理的敘述較好理解，主要是逆元求法。其實思路是模（mi）的整倍數（k）加余數（ai）被Mi整除的最小值。

程序可以將模列表和對應的余數列表，通過輸入獲得。則將上面程序從第44行開始，換成下列程序即可（圖16）。

測試結果與之前相同（圖17）。

有關中國剩余定理問題、數論四大定理問題網上資料非常豐富，有興趣的同學可以參考相關資料，本文不作詳細介紹。如有不當之處，還請各位同仁、朋友斧正。