韓信點兵與中國剩余定理

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

2021/4/111

一、“韓信點兵”的故事和《孫子算經》中的題目

1.“韓信點兵”的故事

韓信閱兵時，讓一隊士兵5人一行排隊從他面前走過，他記下最后一行士兵的人數（1人）；再讓這隊士兵6人一行排隊從他面前走過，他記下最后一行士兵的人數（5人）；再讓這隊士兵7人一行排隊從他面前走過，他記下最后一行士兵的人數（4人），再讓這隊士兵11人一行排隊從他面前走過，他記下最后一行士兵的人數（10人）。然后韓信就憑這些數，可以求得這隊士兵的總人數。2021/4/112

這里面有什么秘密呢？韓信好像非常重視作除法時的余數2021/4/113

2.《孫子算經》中的題目

我國古代數學名著《孫子算經》中有“物不知數”的題目：

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

2021/4/114

這里面又有什么秘密呢？題目給出的條件，也僅僅是作除法時的余數2021/4/115《孫子算經》2021/4/116

二．問題的解答

1．從另一個問題入手問題：今有物不知其數，二二數之剩1，三三數之剩2，四四數之剩3，五五數之剩4，六六數之剩5，七七數之剩6，八八數之剩7，九九數之剩8，問物幾何？2021/4/117

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

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

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

用4除余3）2021/4/118

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

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

尋找規(guī)律的思想

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

2）公倍數法

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

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”的數組成的數列。這個數列實際上是用帶余除法的式子得到的。2021/4/1111

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

2021/4/1112當余時，則，稱為“整除”，或“整除”，這是通常除法“”的另一種表達形式。所以，帶余除法是通常除法的推廣。2021/4/1113

回到求“用2除余1的數”的問題。設這樣的數為，則。這里是被除數，2是除數，是商，1是余，且。2021/4/1114

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

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

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

2021/4/1117

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

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

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

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

2021/4/1122

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

2．《孫子算經》中“有物不知其數”問題的解答

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

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

2）公倍數法現在仿照上邊用過的“公倍數法”，設要求的數為，則依題意，得聯立方程組2021/4/1126

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

2021/4/1128

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

2021/4/1129

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

（或）將代入試算、分析，2021/4/1130最后發(fā)現，為達到目的（三個等式的右邊分別是3，5，7的倍數），最小的加數是82（時）（或最小的減數是23，即時）。2021/4/1131

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

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

多了一個“”，因這時也是正數，合要求。2021/4/1132

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

3）單因子構件湊成法

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

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

2021/4/1137（2）式兩邊同減21變?yōu)?021/4/1138（3）式兩邊同減15變?yōu)?/p>

于是得到

2021/4/1139現在重復一下：所得的x是被3除余1，被5和7除余0的數；y是被5除余1，被3和7除余0的數；z是被7除余1，被3和5除余0的數。2021/4/1140那么，湊出，s不就是我們需要求的數嗎？

2021/4/1141

因為，用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。2021/4/1142

于是我們要求的數是這就是《孫子算經》中“物不知其數”一題的解，有無窮多解，最小的正整數解是23（時）。2021/4/1143

這里，（1），（2），（3）三式分別叫三個“單子因構件”，分別解得每個單因子構件，都是用某一個數去除余1，用另兩個數去除均余0的情況。再據題目要求余數分別是2，3，2的情況，湊成2021/4/1144

所以，上述方法叫“單因子構件湊成法”——解決“由幾個平行條件表述的問題”的方法（也稱“孫子—華方法”）這種方法的最大優(yōu)點是，可以任意改變余數，加以推廣：

題：有物不知其數，三三數之剩a，五五數之剩b，七七數之剩c，問物幾何？

答：解為（的選取應使）.2021/4/11454）歌訣

推廣了的“物不知其數”問題的解為

明朝數學家程大位在《算法統(tǒng)宗》中把上式總結為一首通俗易懂的歌決：

三人同行七十稀，五樹梅花廿一枝，七子團圓正半月，除百零五便得知。其中正半月是指15，這個口訣把3，5，7；70，21，15及105這幾個關鍵的數都總結在內了。詳細說，歌訣的含義是：用3除的余數乘70，5除的余數乘21，7除的余數乘15，相加后再減去（“除”當“減”講）105的適當倍數，就是需要求的（最?。┙饬恕?021/4/1146

當然，解，不是唯一的，每差105，都是另一個解答，但如果結合實際問題，答案往往就是唯一的了。例如一隊士兵的大約人數，韓信應是知道的。2021/4/1147

三、中國剩余定理

1247年南宋的數學家秦九韶把《孫子算經》中“物不知其數”一題的方法推廣到一般的情況，得到稱之為“大衍求一術”的方法，在《數書九章》中發(fā)表。這個結論在歐洲要到十八世紀才由數學家高斯和歐拉發(fā)現。所以世界公認這個定理是中國人最早發(fā)現的，特別稱之為“中國剩余定理”（Chineseremaindertheorem）。2021/4/1148

該定理用現在的語言表達如下：設兩兩互素，設分別被除所得的余數為，則可表示為下式

其中是的最小公倍數；是的公倍數，而且被除所得余數為1；是任意整數。2021/4/1149

要注意的是，用上述定理時，必須兩兩互素。前面的問題中，3，5，7是兩兩互素的，所以“三三數，五五數，七七數”得余數后可用此公式。但“四四數，六六數，九九數”得余數后就不能用此公式，因為4、6、9并不是兩兩互素的。2021/4/1150

“中國剩余定理”不僅有光輝的歷史意義，直到現在還是一個非常重要的定理。1970年，年輕的蘇聯數學家尤里.馬季亞謝維奇（Матиясевич）（28歲）解決了希爾伯特提出的23個問題中的第10個問題，轟動了世界數學界。他在解決這個問題時，用到的知識十分廣泛，而在一個關鍵的地方，就用到了我們的祖先一千多年前發(fā)現的這個“中國剩余定理”。2021/4/1151希爾伯特的第10個問題：丟番圖方程的可解性能求出一個整系數方程的整數根，稱為丟番圖方程可解。希爾伯特問，能否用一種由有限步構成的一般算法判斷一個丟番圖方程的可解性？1970年，蘇聯的IO.B.馬季亞謝維奇證明了希爾伯特所期望的算法不存在。

希爾伯特2021/4/1152四、有趣的應用

某單位有100把鎖，分別編號為1，2，3，…，100。現在要對鑰匙編號，使外單位的人看不懂，而本單位的人一看見鎖的號碼就知道該用哪一把鑰匙。

2021/4/1153

能采用的方法很多，其中一種就是利用中國剩余定理，把鎖的號碼被3，5，7去除所得的三個余數來作鑰匙的號碼（首位余數是0時，也不能省略）。這樣每把鑰匙都有一個三位數編號。例如23號鎖的鑰匙編號是232號，52號鎖的鑰匙編號是123號。2021/4/1154

8號鎖——23119號鎖——14545號鎖——00352號鎖——123因為只有100把鎖，不超過105，所以鎖的號與鑰匙的號是一一對應的。如果希望保密性再強一點兒，則可以把剛才所說的鑰匙編號加上一個固定的常數作為新的鑰匙編號系統(tǒng)。甚至可以每過一個月更換一次這個常數。這樣，仍不破壞鎖的號與鑰匙的號之間的一一對應，而外人則更難知道了。2021/4/1155趣題——找次品：

1）有5個外形相同的乒乓球，其中只有1個重量不標準的次品乒乓球。現再給你一個標準球；請用一架不帶砝碼的天平，最多兩次使用該天平，找出上述次品乒乓球。2021/4/1156最優(yōu)化思想最少次數完成預定任務最大限度發(fā)揮該天平的作用2021/4/1157思考題2021/4/1158趣題——找次品：

2）有12個外形相同的乒乓球，其中只有1個重量不標準的次品乒乓球。請用一架不帶砝碼的天平，最多三次