什么是中國(guó)剩余定理？

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

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

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

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

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

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

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

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

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

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

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

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

中國(guó)剩余定理例題講解2

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

　　答案：

　　方法一：

　　用剩余定理做：

　　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

　　共有：五個(gè)

　　方法二：

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

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

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

　　②因?yàn)槌?余2，因此該數(shù)個(gè)位數(shù)為2或7，根據(jù)①，可知該數(shù)個(gè)位數(shù)應(yīng)為7；

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

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

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

　　一條長(zhǎng)長(zhǎng)的階梯，

　　如果每步跨 2 級(jí)，那么最后余 1 級(jí)；

　　如果每步跨 3 級(jí)，那么最后余 2 級(jí)；

　　如果每步跨 5 級(jí)，那么最后余 4 級(jí)；

　　如果每步跨 6 級(jí)，那么最后余 5 級(jí)；

　　如果每步跨 6 級(jí)，那么最后余 5 級(jí)；

　　只有當(dāng)每步跨7級(jí)時(shí)，最后才剛好走完.

　　問(wèn)這條臺(tái)階最少有 多少 級(jí).

　　答案：

　　如果每步跨 2 級(jí)，那么最后余 1 級(jí)；

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

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

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

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

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

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

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

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

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

的一般解：

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

                 “三人同行七十（７０）稀，
                   五樹梅花二一（２１）枝。
                   七子團(tuán)圓正半月（１５），
                   除百零五（１０５）便得知?！?/p>

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

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

孫子剩余定理-正文

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

式中

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

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

, (1)

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

,

式中k_j滿足

。

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

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

例1、一個(gè)數(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.兩個(gè)條件合并成一個(gè)就是8＋15×整數(shù)，
（3）列出這一串?dāng)?shù)是8， 23， 38，…，
（4）再列出除以7余2的數(shù) 2， 9， 16， 23， 30，…，
就得出符合題目條件的最小數(shù)是23.

例2、有一個(gè)數(shù)，除以3余2，除以4余1，問(wèn)這個(gè)數(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，兩個(gè)條件合并成一個(gè)就是5＋12×整數(shù)
同時(shí)滿足兩個(gè)條件的數(shù)是5、17、29、……（依次增加12）
因此這個(gè)數(shù)除以12的余數(shù)是5.

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

解：（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，兩個(gè)條件合并成一個(gè)就是31＋63×整數(shù)
（4）同時(shí)滿足上兩個(gè)條件的數(shù)有：31，94，157，220，283，346，409，472，535，598，661，724，787，……
（5）上列的數(shù)中，只有157滿足五五數(shù)之余二,
    5、7、9的最小公倍數(shù)是315，
（6）滿足上面三個(gè)條件的數(shù)有：157，472，787，……
（7）只有787滿足二二數(shù)余一，四四數(shù)余二。
所以，滿足條件的數(shù)最小的是787。

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