第三章 第三節(jié) 韓信點兵與中國剩余定理

第三章若干數(shù)學(xué)典故中的數(shù)學(xué)文化第三節(jié)韓信點兵與中國剩余定理1一、“韓信點兵”的故事和兩個有趣的的題目1.“韓信點兵”的故事韓信閱兵時，讓一隊士兵5人一行排隊從他面前走過，他記下最后一行士兵的人數(shù)（1人）；再讓這隊士兵6人一行排隊從他面前走過，他記下最后一行士兵的人數(shù)（5人）；再讓這隊士兵7人一行排隊從他面前走過，他記下最后一行士兵的人數(shù)（4人）；再讓這隊士兵11人一行排隊從他面前走過，他記下最后一行士兵的人數(shù)（10人）．2這里面有什么秘密呢？韓信好像非常重視作除法時的余數(shù)然后韓信就憑這些數(shù)，可以求得這隊士兵的總?cè)藬?shù)。3

今有物不知其數(shù)，三三數(shù)之剩2，五五數(shù)之剩3，七七數(shù)之剩2，問物幾何？

答曰23

2.《孫子算經(jīng)》中的題目我國古代數(shù)學(xué)名著《孫子算經(jīng)》中有“物不知數(shù)”的題目：4這里面又有什么秘密呢？題目給出的條件，也僅僅是作除法時的余數(shù)．中國古代算經(jīng)十書：《周髀算經(jīng)》

《九章算術(shù)》

《海島算經(jīng)》

《

孫子算經(jīng)》

《張邱建算經(jīng)》

《五曹算經(jīng)》

《五經(jīng)算術(shù)》

《數(shù)術(shù)記遺》

《綴術(shù)》

《緝古算經(jīng)》夏侯陽算經(jīng)5

九章算術(shù)周髀算經(jīng)6《孫子算經(jīng)》7公雞每只值五文錢，母雞每只值三文錢，小雞每三只值一文錢．現(xiàn)在用一百文錢買一百只雞。問這一百只雞中，公雞、母雞、小雞各有多少只？

設(shè)買公雞x只，買母雞y只，買小雞z只，那么根據(jù)已知條件列方程，有：

３．張丘建算經(jīng)中的題目x+y+z=100…………（1）

5x+3y+z/3=100……（2）

（2）×3-（1），得

14x+8y=200

也就是7x+4y=100……（3）

8

二．問題的解答

1．從另一個問題入手

問題：今有物不知其數(shù)，二二數(shù)之剩1，三三數(shù)之剩2，四四數(shù)之剩3，五五數(shù)之剩4，六六數(shù)之剩5，七七數(shù)之剩6，八八數(shù)之剩7，九九數(shù)之剩8，問物幾何？9

1）篩法1，3，5，7，9，11，13，15，17，19，21，23，25，27，29，…（

用2除余1）5，11，17，23，29，…（

用3除余2）11，23，…（

用4除余3）10

再從中挑“用5除余4”的數(shù)，…一直篩選下去，舍得下功夫，就一定可得結(jié)果。并且看起來，解，還不是唯一的；可能有無窮多個解。11

化繁為簡的思想當(dāng)問題中有很多類似的條件時，我們先只看其中兩三個條件，這就是化繁為簡。一個復(fù)雜的問題，如果在簡化時仍然保留了原來問題的特點和本質(zhì)，那么簡化就“不失一般性”。學(xué)會“簡化問題”與學(xué)會“推廣問題”一樣，是一種重要的數(shù)學(xué)能力。

尋找規(guī)律的思想

把我們的解題方法總結(jié)為篩法，是重要的進步，是質(zhì)的飛躍：——找到規(guī)律了。篩法是一般性方法，還可以用來解決其他類似的問題。12

數(shù)學(xué)中的化歸方法，就是轉(zhuǎn)化和歸結(jié)的意思，是指把待解決或未解決的數(shù)學(xué)問題，通過某種轉(zhuǎn)化過程，歸結(jié)到一類已經(jīng)解決或者比較容易解決的問題，最終求得問題的解答的一種手段和方法．

化歸的方向是由未知到已知、由難到易、由繁到簡、由暗到明．化歸遵循的原則是熟悉化原則、簡單化原則、具體化原則、正難則反原則．

數(shù)學(xué)問題的解決過程就是不斷地發(fā)現(xiàn)問題、分析問題、直至化歸為一類已經(jīng)能解決或比較容易解決的問題的過程．13

2）公倍數(shù)法

①化繁為簡我們還是先看只有前兩個條件的簡化題目。

1，3，5，7，9，11，13，15，17，19，21，23，25，…（

用2除余1）5，11，17，23，…（

用3除余2）上述篩選過程的第一步，得到:1，3，5，7，9，11，13，15，17，19，21，23，25，…

其實是列出了“用2除余1”的數(shù)組成的數(shù)列。這個數(shù)列實際上是用帶余除法的式子得到的。14

所謂“帶余除法”，是指整數(shù)的如下“除法”：被除數(shù)，除數(shù),必唯一存在商和余，使

15當(dāng)余時，則，稱為“整除”，或“整除”，這是通常除法“”的另一種表達形式。所以，帶余除法是通常除法的推廣。16

回到求“用2除余1的數(shù)”的問題。設(shè)這樣的數(shù)為，則。這里是被除數(shù)，2是除數(shù)，是商，1是余，且。17

這就是“帶余除法”的式子。當(dāng)取時，用上式求得的正好組成上述數(shù)列

1，3，5，7，9，11，13，15，17，19，21，23，25，…

18接著從中篩選出“用3除余2”的數(shù)，就是挑出符合下面“帶余除法”表達式的數(shù)，這里可取0，1，2，3，4，…再繼續(xù)做下去。。。。。。19如果我們不分上面兩步，而是一上來就綜合考慮兩者，則就是要解聯(lián)立方程組

20

那么，為了解這個方程組，除了剛才的篩法外，還有沒有更加巧妙的解法？我們考察上邊兩個方程的特點，發(fā)現(xiàn)，兩個“帶余除法”的式子，都是“余數(shù)比除數(shù)少1”。于是想到，如果把被除數(shù)再加1，不是余數(shù)就為0了嗎？換句話說，不是就出現(xiàn)整除的情況了嗎？21于是把上邊每個方程兩邊都加上1，成為

這說明，既是2的倍數(shù)，又是3的倍數(shù)，因此，它是2與3的公倍數(shù)。由此想到22對整個問題尋找規(guī)律問題：今有物不知其數(shù)，二二數(shù)之剩1，三三數(shù)之剩2，四四數(shù)之剩3，五五數(shù)之剩4，六六數(shù)之剩5，七七數(shù)之剩6，八八數(shù)之剩7，九九數(shù)之剩8，問物幾何？23

②尋找規(guī)律設(shè)問題中，需要求的數(shù)是，則被2，3，4，5，6，7，8，9去除，所得的余數(shù)都是比除數(shù)少1，于是我們把被除數(shù)再加1，則就可被2，3，4，5，6，7，8，9均整除。也就是說，是2,3,4,5,6,7,8,9的公倍數(shù)，從而是其最小公倍數(shù)[2,3,4,5,6,7,8,9]的倍數(shù)。24即

這就是原問題的全部解，有無窮多個解，其中第一個解是2519；我們只取正數(shù)解，因為“物體的個數(shù)”總是正整數(shù)。

25

[思]：①求“用2除余1，3除余2，…用m除余m－1”的數(shù)。②求“用a除余a－1，用b除余b－1，用c除余c－1”的數(shù)。（a,b,c是任意大于1的自然數(shù)）③求“用2，3，4，5，6，7，8，9除都余1”的數(shù)。④求“用5，7，9，11除都余2”的數(shù)。26

2．《孫子算經(jīng)》中“有物不知其數(shù)”問題的解答

問題：今有物不知其數(shù)，三三數(shù)之剩2，五五數(shù)之剩3，七七數(shù)之剩2，問物幾何？271）篩法.2，5，8，11，14，17，20，23，26，29，…（用3除余2）8，23，…（用5除余3）23，…（用7除余2）

由此得到，23是最小的一個解。至于下一個解是什么，要把“…”寫出來才知道；實踐以后發(fā)現(xiàn)，是要費一點兒功夫的。28

2）公倍數(shù)法現(xiàn)在仿照上邊用過的“公倍數(shù)法”，設(shè)要求的數(shù)為，則依題意，得聯(lián)立方程組29

按上一問題中“公倍數(shù)法”解決問題的思路：把方程兩邊同時加上或減去一個什么樣的數(shù)，就能使三個等式的右邊分別是3，5，7的倍數(shù)，從而等式左邊就是3，5，7的公倍數(shù)了。這要通過反復(fù)的試算去完成。30一種試算的方法

31

從第三個等式入手，兩邊加5（或減2）則得

32

則右邊是7的倍數(shù)了，但兩邊加5（或減2）并不能使前兩式的右邊分別是3的倍數(shù)和5的倍數(shù)，所以兩邊加5（或減2）并不能使右邊成為3，5，7的公倍數(shù)。再繼續(xù)從第三個等式入手，為使第三個等式右邊仍然保持是7的倍數(shù)，可再加（或再減），則

（或）將代入試算、分析，33最后發(fā)現(xiàn)，為達到目的（三個等式的右邊分別是3，5，7的倍數(shù)），最小的加數(shù)是82（時）（或最小的減數(shù)是23，即時）。34

用等式兩邊加82來求解，有

用等式兩邊減23來求解，有

多了一個“”，因這時也是正數(shù)，合要求。35

這兩組解是一樣的，都是“23，23+105，23+2×105，……”。原因是82+23=105，故令第一組解就成為便轉(zhuǎn)化成第二組解。36但是，這82和23來之不易；并且如果題目中的余數(shù)變了，就得重新試算，所以這方法缺少一般性，為使它具有一般性，要做根本的修改。37

3）單因子構(gòu)件湊成法

我們先對前幾頁（*）式作兩個方面的簡化：一方面是每次只考慮“一個除式”有余數(shù)的情況（即另兩個除式都是整除的情況）；另一方面是把余數(shù)都簡化為最簡單的1。這樣得到三組方程。38（1）式意味著，在5和7的公倍數(shù)中（35，70，105，…）尋找被3除余1的數(shù)；（2）式意味著，在3和7的公倍數(shù)中（21，42，63，…）尋找被5除余1的數(shù)；（3）式意味著，在3和5的公倍數(shù)中（15，30，45，…）尋找被7除余1的數(shù)。39對（1）式而言，這個數(shù)可以取70，對（2）式而言，這個數(shù)可以取21，對（3）式而言，這個數(shù)可以取15。

于是（1）式兩邊同減70變?yōu)檫@樣：第二式右邊仍是5的倍數(shù)，第三式右邊仍是7的倍數(shù)，而第一式右邊因為減的70是“用3除余1”的數(shù)，正好原來也多一個1，減沒了。第一式右邊也成為了倍數(shù)，是3的倍數(shù)。

40（2）式兩邊同減21變?yōu)?1（3）式兩邊同減15變?yōu)?/p>

于是得到

42現(xiàn)在重復(fù)一下：所得的x是被3除余1，被5和7除余0的數(shù)；y是被5除余1，被3和7除余0的數(shù)；z是被7除余1，被3和5除余0的數(shù)。43那么，湊出，s不就是我們需要求的數(shù)嗎？

44

因為，用3去除s時，除y及除z均余0除3y及除2z均余0，又除x余1除2x余2，∴用3除s時余2。用5去除s時，除x及除z均余0除2x及除2z均余0，又除y余1除3y余3，∴用5除s時余3。用7去除s時，除x及除y均余0除2x及除3y均余0，又除z余1除2z余2，∴用7除s時余2。45

于是我們要求的數(shù)是這就是《孫子算經(jīng)》中“物不知其數(shù)”一題的解，有無窮多解，最小的正整數(shù)解是23（時）。46

這里，（1），（2），（3）三式分別叫三個“單因子構(gòu)件”，分別解得每個單因子構(gòu)件，都是用某一個數(shù)去除余1，用另兩個數(shù)