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

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

ID:14301126

大小:75.50 KB

页数:9页

时间:2018-07-27

韩信点兵又称为中国剩余定理_第1页
韩信点兵又称为中国剩余定理_第2页
韩信点兵又称为中国剩余定理_第3页
韩信点兵又称为中国剩余定理_第4页
韩信点兵又称为中国剩余定理_第5页
资源描述:

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

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、數的乘積加

当前文档最多预览五页,下载文档查看全文

此文档下载收益归作者所有

当前文档最多预览五页,下载文档查看全文
温馨提示:
1. 部分包含数学公式或PPT动画的文件,查看预览时可能会显示错乱或异常,文件下载后无此问题,请放心下载。
2. 本文档由用户上传,版权归属用户,天天文库负责整理代发布。如果您对本文档版权有争议请及时联系客服。
3. 下载前请仔细阅读文档内容,确认文档内容符合您的需求后进行下载,若出现内容与标题不符可向本站投诉处理。
4. 下载文档时可能由于网络波动等原因无法下载或下载错误,付费完成后未能成功下载的用户请联系客服处理。