韩信点兵又称为中国剩余定理

《韩信点兵又称为中国剩余定理》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、簡介：韓信點兵又稱為中國剩餘定理，乃由於相傳漢高祖劉邦問大將軍韓信統御兵士多少，韓信答說，每3人一列餘1人、5人一列餘2人、7人一列餘4人、13人一列餘6人……。劉邦茫然而不知其數。韓信點兵是一個很有趣的猜數遊戲，隨便抓一把蠶豆粒，假若3個一數餘1粒，5個一數餘2粒，7個一數餘2粒，那麼所抓的蠶豆有多少粒?這類題目看起來是很難計算的，可是中國古時卻流傳著一種算法，它的名稱也很多，宋朝周密叫它「鬼谷算」，又名「隔牆算」；楊輝叫它「剪管術」；而比較通行的名稱是「韓信點兵」。最初記述這類算法的是一本名叫「孫子算經」的書，後來在宋朝經過數學家秦九韶的推廣，又發現了一種算法

2、，叫做「大衍求一術」，流傳到西洋以後，外國化稱它是「中國剩餘定理」，在數學史上是極有名的問題。至於它的算法，在「孫子算經」上就已經有了說明：“凡三三數之剩一，則置七十；五五數之剩一，則置二十一；七七數之剩一，則置十五”，而且還流傳著這麼一首歌訣：三人同行七十稀，五樹梅花廿一枝，七子團圓正半月，除百零五便得知。這就是韓信點兵的計算方法，《孫子算經》中給出了其中關鍵的步驟是：但在《孫子算經》中並沒有說明求乘數的方法，直到1247年宋代數學家秦九韶在《數書九章》中才給出具體求法：70是5與7最小公倍的2倍，21、15分別是3與7、3與5最小公倍數的1倍。秦九韶稱這2、1

3、、1的倍數為“乘率”，求出乘率，就可知乘數，意思是說：凡是用3個一數剩下的餘數，將它用70去乘（因為70是5與7的倍數，而又是以3去除餘1的），5個一數剩下的餘數，將它用21去乘（因為21是3與97的倍數，又是以5去除餘1的），7個一數剩下的餘數，將它用15去乘（因為15是3與5的倍數，又是以7去除餘1的），最後將70、5、15這些數加起來，若超過105，就再減掉105，所得的數便是原來的數了。根據這個道理，你就可以很容易地把前面一個題目列成算式：1×70＋2×21＋2×15－105＝142－105＝37。因此你可以知道，原來這一堆蠶豆最少有37粒。孫子算經的作者

4、及確實著作年代均不可考，不過根據考證，著作年代不會在晉朝之後，以這個考證來說上面這種問題的解法，中國人發現得比西方早，所以這個問題的推廣及其解法，被稱為中國剩餘定理。中國剩餘定理（ChineseRemainderTheorem）在近代抽象代數學中佔有一席非常重要的地位。解決問題過程：QUESTION1：有一群人，3人一數剩1人，5人一數剩1人，7人一數剩1人，全部至少有幾人？仔細觀察，我們在數這群人的過程，會發現一個共同點→最後面數完都剩下一人，所以我們可以用下面的式子來表示：某數÷3＝a………1（a≧0）某數÷5＝b………1（b≧0）某數÷7＝c………1（c≧0

5、）我們可以將上面的式子稍微改寫一下，會變成：某數＝a×3＋1………（1）（a≧0）某數＝b×5＋1………（2）（b≧0）某數＝c×7＋1………（3）（c≧0）9從（1）式，我們知道某數可能為1當a=0的時候，當然某數也可能為4當a=1的時候，依此類推，我們可以知道某數可能為1、4、7、10、…中的任何一個。從（2）式，我們知道某數可能為1當b=0的時候，當然某數也可能為6當b=1的時候，依此類推，我們可以知道某數可能為1、6、11、16、…中的任何一個。從（3）式，我們知道某數可能為1當c=0的時候，當然某數也可能為8當c=1的時候，依此類推，我們可以知道某數可能

6、為1、8、15、22、…中的任何一個。我們綜合上面三個式子的發現，將結果表示在下面：012345…7…15…21…35…（1）147101316…22…46…64…106…（2）1611162126…36…76…106…176…（3）1815222936…50…106…148…246…我們由上表發現某數在1與106的地方會發生三個式子都相同的數值，而某數在16、22和36的地方會有兩個式子相同的數值，仔細觀察，我們將整理後的結果呈現如下:16＝5×3＋1＝3×5＋1(1)(2)22＝7×3＋1＝3×7＋1(2)(3)36＝7×5＋1＝5×7＋1(1)(3)從上面的

7、算式我們看出其中存在的一些規律：9因為3與5互質，所以[3,5]＝3跟5的乘積→我們說16是3和5的最小公倍數加1因為3與7互質，所以[3,7]＝3跟7的乘積→我們說22是3和7的最小公倍數加1因為5與7互質，所以[5,7]＝5跟7的乘積→我們說36是5和7的最小公倍數加1由此我們試著將106也使用這種方法來列式得到：（1）106＝35×3＋1（2）106＝21×5＋1（3）106＝15×7＋1上方的三個式子都可用→106＝3×5×7＋1這個式子來表示。(因為35＝5×7，21＝3×7，15＝3×5)我們可以說，106是3、5、7中任意2個數的最小公倍數乘上另外一

8、數的乘積加