什么是中國剩余定理

什么是中國剩余定理

上傳: 鄺壬香 更新時間：2012-11-29 17:39:55

什么是中國剩余定理？

剩余定理詳細(xì)解法

中國數(shù)學(xué)史書上記載：在兩千多年前的我國古代算書《孫子算經(jīng)》中，有這樣一個問題及其解法：

今有物不知其數(shù)，三三數(shù)之剩二；五五數(shù)之剩三：七七數(shù)之剩二。問物幾何？

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

如果七個七個的數(shù)最后剩二個，問這堆東西有多少個？ 你知道這個數(shù)目嗎？

《孫子算經(jīng)》這道著名的數(shù)學(xué)題是我國古代數(shù)學(xué)思想“大衍求一術(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ù)，當(dāng)70×2

時被3除余2 21是可以被3、7整除且被5除余1的最小正整數(shù)，當(dāng)21×3時被5除余3 15是可以被3、5整除且被7除

余1的最小正整數(shù)，當(dāng)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ù)學(xué)古書「孫子算經(jīng)」也有類似的問題：

「今有物，不知其數(shù)，三三數(shù)之，剩二，五五數(shù)之，剩三，七七數(shù)之，剩二，問物幾何？」答曰：「二十三」 術(shù)

曰：「三三數(shù)之剩二，置一百四十，五五數(shù)之剩三，置六十三，七七數(shù)之剩二，置三十，并之，得二百三十三，以二百

一十減之，即得。凡三三數(shù)之剩一，則置七十，五五數(shù)之剩一，則置二十一，七七數(shù)之剩一，則置十五，即得。」

孫子算經(jīng)的作者及確實著作年代均不可考，不過根據(jù)考證，著作年代不會在晉朝之后，以這個考證來說上面這種問

題的解法，中國人發(fā)現(xiàn)得比西方早，所以這個問題的推廣及其解法，被稱為中國剩余定理。

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

中國剩余定理例題講解1

中國剩余定理例題講解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ù)。

①因為除以4余3，因此該數(shù)為奇數(shù)；

②因為除以5余2，因此該數(shù)個位數(shù)為2或7，根據(jù)①，可知該數(shù)個位數(shù)應(yīng)為7；

③因為除以9余7，結(jié)合②，該數(shù)最少應(yīng)為97；結(jié)合①，經(jīng)過嘗試，得到符合條件的最小數(shù)值為187

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

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

關(guān)于 中國剩余定理 的一道數(shù)學(xué)題

一條長長的階梯，

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

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

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

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

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

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

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

答案：

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

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

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

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

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

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

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

在中國數(shù)學(xué)史上，廣泛流傳著一個“韓信點兵”的故事：

韓信是漢高祖劉邦手下的大將，他英勇善戰(zhàn)，智謀超群，為漢朝的建立了卓絕的功勞。據(jù)說韓信的數(shù)學(xué)水平也非常高

超，他在點兵的時候，為了保住軍事機密，不讓敵人知道自己部隊的實力，先令士兵從1至3報數(shù)，然后記下最后一個

士兵所報之?dāng)?shù)；再令士兵從１至５報數(shù)，也記下最后一個士兵所報之?dāng)?shù)；最后令士兵從1至7報數(shù)，又記下最后一個士

兵所報之?dāng)?shù)；這樣，他很快就算出了自己部隊士兵的總?cè)藬?shù)，而敵人則始終無法弄清他的部隊究竟有多少名士兵。

這個故事中所說的韓信點兵的計算方法，就是現(xiàn)在被稱為“中國剩余定理”的一次同余式解法。它是中國古代數(shù)學(xué)家的

一項重大創(chuàng)造，在世界數(shù)學(xué)史上具有重要的地位。

最早提出并記敘這個數(shù)學(xué)問題的，是南北朝時期的數(shù)學(xué)著作《孫子算經(jīng)》中的“物不知數(shù)”題目。這道“物不知數(shù)”的題

目是這樣的：

“今有一些物不知其數(shù)量。如果三個三個地去數(shù)它，則最后還剩二個；如果五個五個地去數(shù)它，則最后還剩三個；如

果七個七個地去數(shù)它，則最后也剩二個。問：這些物一共有多少？”

用簡練的數(shù)學(xué)語言來表述就是：求這樣一個數(shù)，使它被３除余２，被５除余３，被７除余２。《孫子算經(jīng)》給出了這

道題目的解法和答案，用算式表示即為：

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

道：

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

的一般解：

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

“三人同行七十（７０）稀，

五樹梅花二一（２１）枝。

七子團(tuán)圓正半月（１５），

除百零五（１０５）便得知。”

《孫子算經(jīng)》的“物不知數(shù)”題雖然開創(chuàng)了一次同余式研究的先河，但由于題目比較簡單，甚至用試猜的方法也能求得，

所以尚沒有上升到一套完整的計算程序和理論的高度。真正從完整的計算程序和理論上解決這個問題的，是南宋時期的

數(shù)學(xué)家秦九韶。秦

九韶在他的《數(shù)書九章》（見圖１一７一１）中提出了一個數(shù)學(xué)方法“大衍求一術(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ù)學(xué)概念，并詳細(xì)敘述了“大衍求一術(shù)”的完整過程。（由于解法過于繁細(xì)，我們在

這里就不展開敘述了，有興趣的讀者可進(jìn)一步參閱有關(guān)書籍。）直到此時，由《孫子算經(jīng)》“物不知數(shù)”題開創(chuàng)的一次同

余式問題，才真正得到了一個普遍的解法，才真正上升到了

“中國剩余定理”的高度。

從《孫子算經(jīng)》到秦九韶《數(shù)書九章》對一次同余式問題的研究成果，在１９世紀(jì)中期開始受到西方數(shù)學(xué)界的重視。

１８５２年，英國傳教士偉烈亞力向歐洲介紹了《孫子算經(jīng)》的“物不知數(shù)”題和秦九韶的“大衍求一術(shù)”；１８７６年，

德國人馬蒂生指出，中國的這一解法與西方１９世紀(jì)高斯《算術(shù)探究》中關(guān)于一次同余式組的解法完全一致。從此，中

國古代數(shù)學(xué)的這一創(chuàng)造逐漸受到世界學(xué)者的矚目，并在西方數(shù)學(xué)史著作中正式被稱為“中國剩余定理”。

孫子剩余定理-正文

中國南北朝時期（5～6世紀(jì)）著名的著作《孫子算經(jīng)》中“物不知數(shù)”問題所闡述的定理。物不知數(shù)問題的原題是：

“今有物，不知其數(shù)，三三數(shù)之剩二，五五數(shù)之剩三，七七數(shù)之剩二，問物幾何？”這屬于數(shù)論的一次同余方程組問題。

用現(xiàn)代數(shù)學(xué)符號可表為求下列同余方程的整數(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為適當(dāng)選取的整數(shù),使得0＜N ≤105，這里取p=2。

上述問題和解法，可直接推廣為定理：設(shè)α,α兩兩互素， 則

12n

,…,α

, (1)

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

,

式中k滿足

j

。

p為適當(dāng)選取的整數(shù),使得N≤M。“物不知數(shù)”問題,在歐洲是一個知名的問題，C.F.高斯于19世紀(jì)初給出了它的一般性定

理。因此國際上稱上述《孫子算經(jīng)》中的問題為孫子剩余定理或中國剩余定理。

《孫子算經(jīng)》沒有給出求k的具體算法。宋代秦九韶在《數(shù)書九章》中第一次詳細(xì)地、完整地闡述了求解一次同余

j

方程組的算法，他稱做“大衍總數(shù)術(shù)”，其中包括求k的一種機械化算法──大衍求一術(shù)。

j

秦九韶稱α為“定數(shù)”，k為“乘率”,由 中屢減α所得的余數(shù)G(<α)為“奇數(shù)”。“大衍求一術(shù)云：置奇右上，定居右

jjjjj

下,立天元一于左上(圖1 )。先以右上除右下，所得商數(shù)與左上一相生(即相乘)入左下。然后乃以右行上下以少除

多，遞互除之，所得商數(shù)隨即遞互累乘歸左行上下，須使右上末后奇一而止。乃驗左上所得，以為乘率。”秦九韶在例

題中曾以G=3,α=4為例，列出求k的算草布式：

jjj

此時右上余1，故左上即為乘率k=3。

j

秦九韶還在歷史上首次提出了當(dāng) α,α并非兩兩互素時, 求解(1)的方法。他設(shè)計了“兩兩連環(huán)求等,約奇弗約偶”，

12n

,…,α

"復(fù)乘求定"等算法,先約去諸模數(shù)α,α中包含的多余的因子,得到新的一組 ,

12n

,…,α

使 恰為 α,α的最小公倍數(shù)。再對 ,中的因子重新歸并，得

到 使 仍為α,α的最小公倍數(shù)，且它們兩兩互素。這樣便將問題化約為模數(shù)

12n

,…,α

12n

,…,α

兩兩互素的情形。秦九韶尚未提及當(dāng)α,α并非兩兩互素時，方程(1)可解的條件。但從他所舉八道例題中有七道的

12n

,…,α

模數(shù)滿足可解條件這一事實分析，許多人認(rèn)為秦九韶已知道該條件。

例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）列出這一串?dāng)?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。

練習(xí)：

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ù)