孫子定理的Python簡(jiǎn)單分析與應(yīng)用

王薇　王德貴

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

一元線性同余方程組問(wèn)題最早見于中國(guó)南北朝時(shí)期（公元5世紀(jì)）的數(shù)學(xué)著作《孫子算經(jīng)》卷下第二十六題，叫作“物不知數(shù)”問(wèn)題，原文：

有物不知其數(shù)，三三數(shù)之剩二，五五數(shù)之剩三，七七數(shù)之剩二。問(wèn)物幾何？即，一個(gè)整數(shù)除以三余二，除以五余三，除以七余二，求這個(gè)整數(shù)?！秾O子算經(jīng)》中首次提到了同余方程組問(wèn)題，以及以上具體問(wèn)題的解法，因此在中文數(shù)學(xué)文獻(xiàn)中也會(huì)將中國(guó)剩余定理稱為孫子定理。

用現(xiàn)代數(shù)學(xué)的語(yǔ)言來(lái)說(shuō)明的話，孫子定理給出了以下的一元線性同余方程組：

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

整數(shù)x同余于a1模m1，即x%m1 = a1%m1，……

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

對(duì)于整數(shù)，數(shù)學(xué)家們一直很熱衷于整除、因數(shù)、余數(shù)和素?cái)?shù)等方面的研究，因而也出現(xiàn)了數(shù)論四大定理等很多相關(guān)的定理和猜想。在這四大定理之中，我們已經(jīng)用Python驗(yàn)證了費(fèi)馬小定理和威爾遜定理，今天我們就利用Python由簡(jiǎn)單入手，來(lái)求解孫子定理相關(guān)的問(wèn)題。

設(shè)計(jì)思路是由淺入深，先研究?jī)蓚€(gè)條件的簡(jiǎn)單問(wèn)題求解方法，然后在此基礎(chǔ)上，再討論多個(gè)條件的情況，最后討論孫子定理及應(yīng)用。

程序設(shè)計(jì)涉及的是等級(jí)考試四級(jí)和二級(jí)內(nèi)容。

（1）余同加余

一數(shù)除以3余1，除以4余1，求這數(shù)。

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

（2）和同加和

一數(shù)除以3余2，除以4余1，求這數(shù)。

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

（3）差同減差

一數(shù)除以3余1，除以4余2，求這數(shù)。

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

（4）其他情況

一數(shù)除以3余1，除以4余3，求這數(shù)。

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

（5）程序設(shè)計(jì)

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

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

在兩個(gè)條件的基礎(chǔ)上，擴(kuò)展到三個(gè)及三個(gè)以上的條件時(shí)，也可以用枚舉法，則需要解決以下問(wèn)題。

（1）輸入數(shù)據(jù)：多組數(shù)據(jù)存儲(chǔ)在列表中，m存儲(chǔ)模，a存儲(chǔ)余數(shù)。因?yàn)檩敵鰲l件不定，所以用while循環(huán)，以回車結(jié)束輸入。

然后比較余數(shù)和模，如果余數(shù)大于模，重新輸入數(shù)據(jù)。

（2）判斷互素：多組模值，依次判斷是否兩兩互素?？梢愿鶕?jù)最大公約數(shù)來(lái)判斷。

（3）枚舉：通過(guò)枚舉滿足第一個(gè)條件的數(shù)，依次判斷是否滿足其他條件。當(dāng)所有的條件都滿足，則終止循環(huán)，輸出x值。

根據(jù)以上分析，編寫程序如圖3。

驗(yàn)證結(jié)果（圖4）。

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

這是一道經(jīng)典的問(wèn)題，前面已經(jīng)求出滿足條件的最小值為23。因?yàn)槭勘鴳?yīng)該在1000多人左右，所以再加上3×5×7=105的倍數(shù)就可以了，所以加上1050，韓信的士兵人數(shù)為1073人。

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

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

（1）同余定理

最先引用同余的概念與符號(hào)者為德國(guó)數(shù)學(xué)家高斯。同余理論是初等數(shù)論的重要組成部分，是研究整數(shù)問(wèn)題的重要工具之一。

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

記作：a≡b （mod m），

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

顯然，有如下性質(zhì)：

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）對(duì)稱性：若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）孫子定理內(nèi)容

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

（3）程序設(shè)計(jì)

為了方便大家理解，我們分步設(shè)計(jì)程序。

①最大公約數(shù)

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

②判斷互素（圖7）

遍歷列表m，通過(guò)自定義函數(shù)，判斷是否互素時(shí)調(diào)用最大公約數(shù)函數(shù)，如果為1，則為互素。

③求mi乘積M

遍歷列表m，求各項(xiàng)的積（圖8）。

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

⑤求Mi逆元（數(shù)論倒數(shù)）存儲(chǔ)在列表Mi_[ ]中

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

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

⑦定義模和余數(shù)列表，并調(diào)用自定義函數(shù)，輸出結(jié)果（圖12）

⑧測(cè)試結(jié)果（圖13、圖14）

與前測(cè)試結(jié)果相同。

完整程序，如圖15。

三、測(cè)試與改進(jìn)

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

程序可以將模列表和對(duì)應(yīng)的余數(shù)列表，通過(guò)輸入獲得。則將上面程序從第44行開始，換成下列程序即可（圖16）。

測(cè)試結(jié)果與之前相同（圖17）。

有關(guān)中國(guó)剩余定理問(wèn)題、數(shù)論四大定理問(wèn)題網(wǎng)上資料非常豐富，有興趣的同學(xué)可以參考相關(guān)資料，本文不作詳細(xì)介紹。如有不當(dāng)之處，還請(qǐng)各位同仁、朋友斧正。