什么是中國剩余定理？

　　中國數(shù)學史書上記載：在兩千多年前的我國古代算書《孫子算經(jīng)》中，有這樣一個問題及其解法：
　　今有物不知其數(shù)，三三數(shù)之剩二；五五數(shù)之剩三：七七數(shù)之剩二。問物幾何？

　　意思 是說：現(xiàn)在有一堆東西，不知道它的數(shù)量，如果三個三個的數(shù)最后剩二個，如果五個五個的數(shù)最后剩三個，如果七個七個的數(shù)最后剩二個，問這堆東西有多少個？ 你知道這個數(shù)目嗎？

　　《孫子算經(jīng)》這道著名的數(shù)學題是我國古代數(shù)學思想“大衍求一術(shù)”的 具體體現(xiàn)，針對這道題給出的解法是： N=70×2＋21×3＋15×2-2×105＝23

　　如此巧妙的解法的關(guān)鍵是數(shù)字70、21和15的選擇： 70是可以被5、7整除且被3除余1的最小正整數(shù)，當70×2時被3除余2 21是可以被3、7整除且被5除余1的最小正整數(shù)，當21×3時被5除余3 15是可以被3、5整除且被7除余1的最小正整數(shù)，當15×2時被7除余2 通過這種構(gòu)造方法得到的N就可以滿足題目的要求而減去2×105 后得到的是滿足這一條件的最小正整數(shù)。

　　韓信點兵又稱為中國剩余定理，相傳漢高祖劉邦問大將軍韓信統(tǒng)御兵士多少，韓信答說，每3人一列余1人、5人一列余2人、7人一列余4人、13人一列余6人……。

　　劉邦茫然而不知其數(shù)。

　　我們先考慮下列的問題：假設(shè)兵不滿一萬，每5人一列、9人一列、13人一列、17人一列都剩3人，則兵有多少？

　　首先我們先求5、9、13、17之最小公倍數(shù)9945（注：因為5、9、13、17為兩兩互質(zhì)的整數(shù)，故其最小公倍數(shù)為這些數(shù)的積），然后再加3，得9948（人）。

　　中國有一本數(shù)學古書「孫子算經(jīng)」也有類似的問題：

　　「今有物，不知其數(shù)，三三數(shù)之，剩二，五五數(shù)之，剩三，七七數(shù)之，剩二，問物幾何？」答曰：「二十三」 術(shù)曰：「三三數(shù)之剩二，置一百四十，五五數(shù)之剩三，置六十三，七七數(shù)之剩二，置三十，并之，得二百三十三，以二百一十減之，即得。凡三三數(shù)之剩一，則置七十，五五數(shù)之剩一，則置二十一，七七數(shù)之剩一，則置十五，即得?！?/p>

　　孫子算經(jīng)的作者及確實著作年代均不可考，不過根據(jù)考證，著作年代不會在晉朝之后，以這個考證來說上面這種問題的解法，中國人發(fā)現(xiàn)得比西方早，所以這個問題的推廣及其解法，被稱為中國剩余定理。

　　中國剩余定理（Chinese Remainder Theorem）在近代抽象代數(shù)學中占有一席非常重要的地位。

中國剩余定理例題講解2

　　一個三位數(shù)除以9余7，除以5余2，除以4余3，這樣的三位數(shù)共有幾個？

　　答案：

　　方法一：

　　用剩余定理做：

　　7*100+2*36+3*45=907

　　9、5、4的最小公倍數(shù)是：180 907/180=5。。。7

　　所以這樣的三位數(shù)是：180*1+7=187 180*2+7=367 180*3+7=547 180*4+7=727 180*5+7=907

　　共有：五個

　　方法二：

　　枚舉法： 類似題型若無特殊的條件，一般都通過枚舉法找出符合條件的最小值，然后在此基礎(chǔ)上加上各除數(shù)的最小公倍數(shù)，則可以得出相應(yīng)的答案。

　　具體到此題，我們可以利用一些特殊條件縮小范圍，減少枚舉次數(shù)。

　?、僖驗槌?余3，因此該數(shù)為奇數(shù)；

　?、谝驗槌?余2，因此該數(shù)個位數(shù)為2或7，根據(jù)①，可知該數(shù)個位數(shù)應(yīng)為7；

　?、垡驗槌?余7，結(jié)合②，該數(shù)最少應(yīng)為97；結(jié)合①，經(jīng)過嘗試，得到符合條件的最小數(shù)值為187

　?、?個除數(shù)9、5、4的最小公倍數(shù)180，

　　因此符合條件的三位數(shù)有187、367、547、727、907共5個。

　　一條長長的階梯，

　　如果每步跨 2 級，那么最后余 1 級；

　　如果每步跨 3 級，那么最后余 2 級；

　　如果每步跨 5 級，那么最后余 4 級；

　　如果每步跨 6 級，那么最后余 5 級；

　　如果每步跨 6 級，那么最后余 5 級；

　　只有當每步跨7級時，最后才剛好走完.

　　問這條臺階最少有 多少 級.

　　答案：

　　如果每步跨 2 級，那么最后余 1 級；

　　可知 是個奇數(shù)如果每步跨 3 級，那么最后余 2 級；

　　可知+1就是3的整數(shù)倍如果每步跨 5 級，那么最后余 4 級；

　　可知尾是4或9.但是是個奇數(shù),所以是9如果每步跨 6 級，那么最后余 5 級；

　　可知+1就是6的整數(shù)倍只有當每步跨7級時，最后才剛好走完.

　　可知是7的整數(shù)倍7*7=49  7*17=119  49+1不是3的倍數(shù),排除了.

　　119+1是3和6的整數(shù)倍,所以臺階有119級

在中國數(shù)學史上，廣泛流傳著一個“韓信點兵”的故事：
    韓信是漢高祖劉邦手下的大將，他英勇善戰(zhàn)，智謀超群，為漢朝的建立了卓絕的功勞。據(jù)說韓信的數(shù)學水平也非常高超，他在點兵的時候，為了保住軍事機密，不讓敵人知道自己部隊的實力，先令士兵從1至3報數(shù)，然后記下最后一個士兵所報之數(shù)；再令士兵從１至５報數(shù)，也記下最后一個士兵所報之數(shù)；最后令士兵從1至7報數(shù)，又記下最后一個士兵所報之數(shù)；這樣，他很快就算出了自己部隊士兵的總?cè)藬?shù)，而敵人則始終無法弄清他的部隊究竟有多少名士兵。
    這個故事中所說的韓信點兵的計算方法，就是現(xiàn)在被稱為“中國剩余定理”的一次同余式解法。它是中國古代數(shù)學家的一項重大創(chuàng)造，在世界數(shù)學史上具有重要的地位。
    最早提出并記敘這個數(shù)學問題的，是南北朝時期的數(shù)學著作《孫子算經(jīng)》中的“物不知數(shù)”題目。這道“物不知數(shù)”的題目是這樣的：
   “今有一些物不知其數(shù)量。如果三個三個地去數(shù)它，則最后還剩二個；如果五個五個地去數(shù)它，則最后還剩三個；如果七個七個地去數(shù)它，則最后也剩二個。問：這些物一共有多少？”
    用簡練的數(shù)學語言來表述就是：求這樣一個數(shù)，使它被３除余２，被５除余３，被７除余２?！秾O子算經(jīng)》給出了這道題目的解法和答案，用算式表示即為：

用現(xiàn)代的數(shù)學術(shù)語來說，這幅“開方作法本源圖”實際上是一個指數(shù)為正整數(shù)的二項式定理系數(shù)表。稍懂代數(shù)的讀者都知道：

《孫子算經(jīng)》實際上是給出了這類一次同余式組

的一般解：

其中70、21、15和105這四個數(shù)是關(guān)鍵，所以后來的數(shù)學家把這種解法編成了如下的一首詩歌以便于記誦：

                 “三人同行七十（７０）稀，
                   五樹梅花二一（２１）枝。
                   七子團圓正半月（１５），
                   除百零五（１０５）便得知。”

《孫子算經(jīng)》的“物不知數(shù)”題雖然開創(chuàng)了一次同余式研究的先河，但由于題目比較簡單，甚至用試猜的方法也能求得，所以尚沒有上升到一套完整的計算程序和理論的高度。真正從完整的計算程序和理論上解決這個問題的，是南宋時期的數(shù)學家秦九韶。秦
九韶在他的《數(shù)書九章》（見圖１一７一１）中提出了一個數(shù)學方法“大衍求一術(shù)”，系統(tǒng)地論述了一次同余式組解法的基本原理和一般程序。
     秦九韶為什么要把他的這一套計算程序和基本原理稱為“大衍求一術(shù)”呢？這是因為其計算程序的核心問題是要“求一”。所謂“求一”，通俗他說，就是求“一個數(shù)的多少倍除以另一個數(shù)，所得的余數(shù)為一”。那么為什么要“求一”呢？我們可以從“物不知數(shù)”題的幾個關(guān)鍵數(shù)字７０、２１、１５中找到如下的規(guī)律：

其中70是5和7的倍數(shù)，但被3除余1；21是3和7的倍數(shù)，但被5除余1；15是3和5的倍數(shù)，但被7除余1，任何一個一次同余式組，只要根據(jù)這個規(guī)律求出那幾個關(guān)鍵數(shù)字，那么這個一次同余式組就不難解出了。為此，秦九韶提出了乘率、定數(shù)、衍母、衍數(shù)等一系列數(shù)學概念，并詳細敘述了“大衍求一術(shù)”的完整過程。（由于解法過于繁細，我們在這里就不展開敘述了，有興趣的讀者可進一步參閱有關(guān)書籍。）直到此時，由《孫子算經(jīng)》“物不知數(shù)”題開創(chuàng)的一次同余式問題，才真正得到了一個普遍的解法，才真正上升到了
“中國剩余定理”的高度。
    從《孫子算經(jīng)》到秦九韶《數(shù)書九章》對一次同余式問題的研究成果，在１９世紀中期開始受到西方數(shù)學界的重視。１８５２年，英國傳教士偉烈亞力向歐洲介紹了《孫子算經(jīng)》的“物不知數(shù)”題和秦九韶的“大衍求一術(shù)”；１８７６年，德國人馬蒂生指出，中國的這一解法與西方１９世紀高斯《算術(shù)探究》中關(guān)于一次同余式組的解法完全一致。從此，中國古代數(shù)學的這一創(chuàng)造逐漸受到世界學者的矚目，并在西方數(shù)學史著作中正式被稱為“中國剩余定理”。

孫子剩余定理-正文

　　中國南北朝時期（5～6世紀）著名的著作《孫子算經(jīng)》中“物不知數(shù)”問題所闡述的定理。物不知數(shù)問題的原題是：“今有物，不知其數(shù)，三三數(shù)之剩二，五五數(shù)之剩三，七七數(shù)之剩二，問物幾何？”這屬于數(shù)論的一次同余方程組問題。用現(xiàn)代數(shù)學符號可表為求下列同余方程的整數(shù)解：

式中

　　《孫子算經(jīng)》中使用一種適合解一般的一次同余方程組的方法，求得此特殊問題的最小整數(shù)解N=23。解題步驟是：選定5×7的一個倍數(shù)，被3除余1，即70；選定3×7的一個倍數(shù)，被5除余1，即21；選定3×5的一個倍數(shù)，被7除余1，即15。然后按下式計算

式中105為3,5,7的最小公倍數(shù)，p為適當選取的整數(shù),使得0＜N ≤105，這里取p=2。
　　上述問題和解法，可直接推廣為定理：設(shè)α₁,α₂,…,α_n兩兩互素， 則

, (1)

有整數(shù)解,且對模M是惟一的。若記最小正整數(shù)解為N,則

,

式中k_j滿足

。

p為適當選取的整數(shù),使得N≤M?！拔锊恢獢?shù)”問題,在歐洲是一個知名的問題，C.F.高斯于19世紀初給出了它的一般性定理。因此國際上稱上述《孫子算經(jīng)》中的問題為孫子剩余定理或中國剩余定理。
　　《孫子算經(jīng)》沒有給出求k_j的具體算法。宋代秦九韶在《數(shù)書九章》中第一次詳細地、完整地闡述了求解一次同余方程組的算法，他稱做“大衍總數(shù)術(shù)”，其中包括求k_j的一種機械化算法──大衍求一術(shù)。
　　秦九韶稱α_j為“定數(shù)”，k_j為“乘率”,由 中屢減α_j所得的余數(shù)G_j(<α_j)為“奇數(shù)”?！按笱芮笠恍g(shù)云：置奇右上，定居右下,立天元一于左上(圖1 )。先以右上除右下，所得商數(shù)與左上一相生(即相乘)入左下。然后乃以右行上下以少除多，遞互除之，所得商數(shù)隨即遞互累乘歸左行上下，須使右上末后奇一而止。乃驗左上所得，以為乘率?！鼻鼐派卦诶}中曾以G_j=3,α_j=4為例，列出求k_j的算草布式：

此時右上余1，故左上即為乘率k_j=3。
　　秦九韶還在歷史上首次提出了當 α₁,α₂,…,α_n并非兩兩互素時, 求解(1)的方法。他設(shè)計了“兩兩連環(huán)求等,約奇弗約偶”，"復乘求定"等算法,先約去諸模數(shù)α₁,α₂,…,α_n中包含的多余的因子,得到新的一組 ,使 恰為 α₁,α₂,…,α_n的最小公倍數(shù)。再對 ,中的因子重新歸并，得到 使 仍為α₁,α₂,…,α_n的最小公倍數(shù)，且它們兩兩互素。這樣便將問題化約為模數(shù)兩兩互素的情形。秦九韶尚未提及當α₁,α₂,…,α_n并非兩兩互素時，方程(1)可解的條件。但從他所舉八道例題中有七道的模數(shù)滿足可解條件這一事實分析，許多人認為秦九韶已知道該條件。

例1、一個數(shù)除以3余2，除以5余3，除以7余2，求符合條件的最小數(shù).
解：（1）先列出除以3余2的數(shù)：2， 5， 8， 11， 14， 17， 20， 23， 26，…，
（2）再列出除以5余3的數(shù)：3， 8， 13， 18， 23， 28，….
這兩列數(shù)中，首先出現(xiàn)的公共數(shù)是8。
3與5的最小公倍數(shù)是15.兩個條件合并成一個就是8＋15×整數(shù)，
（3）列出這一串數(shù)是8， 23， 38，…，
（4）再列出除以7余2的數(shù) 2， 9， 16， 23， 30，…，
就得出符合題目條件的最小數(shù)是23.

例2、有一個數(shù)，除以3余2，除以4余1，問這個數(shù)除以12余幾？

解：（1）除以3余2的數(shù)有：2， 5， 8， 11，14， 17， 20， 23….
（2）除以4余1的數(shù)有：1， 5， 9， 13， 17， 21， 25， 29，….
（3）這兩列數(shù)中，首先出現(xiàn)的公共數(shù)是5。
3和4的最小公倍數(shù)是12，兩個條件合并成一個就是5＋12×整數(shù)
同時滿足兩個條件的數(shù)是5、17、29、……（依次增加12）
因此這個數(shù)除以12的余數(shù)是5.

例3、今有物不知其數(shù)，二二數(shù)之余一，四四數(shù)之余三，五五數(shù)之余二，七七數(shù)之余三，九九數(shù)之余四，問物幾何？

解：（1）九九數(shù)之余四,可能的數(shù)是：13，22，31，40，49，58，……
（2）七七數(shù)之余三,可能的數(shù)是：10，17，24，31，……
（3）這兩列數(shù)中，首先出現(xiàn)的公共數(shù)是31。
9和7的最小公倍數(shù)是63，兩個條件合并成一個就是31＋63×整數(shù)
（4）同時滿足上兩個條件的數(shù)有：31，94，157，220，283，346，409，472，535，598，661，724，787，……
（5）上列的數(shù)中，只有157滿足五五數(shù)之余二,
    5、7、9的最小公倍數(shù)是315，
（6）滿足上面三個條件的數(shù)有：157，472，787，……
（7）只有787滿足二二數(shù)余一，四四數(shù)余二。
所以，滿足條件的數(shù)最小的是787。

練習：
1、一個數(shù)除以3余2，除以5余3，除以7余2，求滿足條件的最小數(shù)？
2、滿足除以5余1，除以7余3，除以8余5的最小自然數(shù)。
3、在10000以內(nèi)，除以3余2，除以7余3，除以11余4的數(shù)有多少個？
4、求滿足除以6余3，除以8余5，除以9余6的最小自然數(shù)。
5、一卷彩帶，如果剪成2分米或3分米或5分米或6分米都剩1分米，如剪成每段為7分米正好不剩。這卷彩帶至少多少米？
6、一個數(shù)除以5余4，除以8余3，除以11余2，求滿足條件的最小的自然數(shù)。
7、有一堆蘋果，3個3個數(shù)余1個，5個5個數(shù)余2個，6個6個數(shù)余4個。這堆蘋果至少有多少個？
8、在小于1000的自然數(shù)中，除以4余3，除以5余2，除以7余4的最大自然數(shù)是多少？
9、在5000以內(nèi)，除以3余1，除以5余2，除以7余3的自然數(shù)有多少個
10、有一個兩位數(shù)，除以2與除以3都余1，除以4與除以5都余3，求這個數(shù)