第三模塊重點學習內(nèi)容韓信點兵與剩余定理

1、1,第三模塊重點學習內(nèi)容韓信點兵與中國剩余定理,2,韓信是中國古代一位有名的大元帥。他少年時就父母雙亡，生活困難，曾靠乞討為生，還經(jīng)常受到某些潑皮的欺凌，胯下之辱講的就是韓信少年時被潑皮強迫從胯下鉆過的事。后來他投奔劉邦，展現(xiàn)了他杰出的軍事才能，為劉邦打敗了楚霸王項羽立下汗馬功勞，開創(chuàng)了劉漢皇朝四百年的基業(yè)。民間流傳著一些以韓信為主角的有關(guān)聰明人的故事，韓信點兵的故事就是其中的一個。,一、“韓信點兵”的故事與《孫子算經(jīng)》中的題目

2、,3,相傳有一次，韓信將1500名將士與楚王大將李鋒交戰(zhàn)。雙方大戰(zhàn)一場，楚軍不敵，敗退回營。而漢軍也有傷亡，只是一時還不知傷亡多少。于是，韓信整頓兵馬也返回大本營，準備清點人數(shù)。當行至一山坡時，忽有后軍來報，說有楚軍騎兵追來。韓信馳上高坡觀看，只見遠方塵土飛揚，殺聲震天。漢軍本來已經(jīng)十分疲憊了，這時不由得人心大亂。韓信仔細地觀看敵方，發(fā)現(xiàn)來敵不足五百騎，便急速點兵迎敵。不一會兒，值日副官報告，共有1035人。他還不放心，決定自己親自算一

3、下。,1.“韓信點兵”的故事,4,韓信閱兵時，讓一隊士兵5人一行排隊從他面前走過，他記下最后一行士兵的人數(shù)（1人）；再讓這隊士兵6人一行排隊從他面前走過，他記下最后一行士兵的人數(shù)（5人）；再讓這隊士兵7人一行排隊從他面前走過，他記下最后一行士兵的人數(shù)（4人），再讓這隊士兵11人一行排隊從他面前走過，他記下最后一行士兵的人數(shù)（10人）。然后韓信就憑這些數(shù)，可以求得這隊士兵的總?cè)藬?shù)。,思考題：這里面有什么秘密呢？韓信好像非常重視作除法時的余

4、數(shù)。 “數(shù)的除法運算以及余數(shù)”是小學數(shù)學的內(nèi)容?，F(xiàn)在，每個學生都具有這樣的基礎，但能否會運用就有差別了，你能夠分析它嗎？,5,約成書于四、五世紀，作者生平和編寫年代都不清楚。現(xiàn)在傳本的《孫子算經(jīng)》共三卷。卷上敘述算籌記數(shù)的縱橫相間制度和籌算乘除法則，卷中舉例說明籌算分數(shù)算法和籌算開平方法。卷下第31題，可謂是后世“雞兔同籠”題的始祖，后來傳到日本，變成“鶴龜算”。,2.《孫子算經(jīng)》,書中是這樣敘述的：“今有雞兔同籠，上有三十五頭，下有九

5、十四足，問雞兔各幾何？這四句話的意思是：有若干只雞兔同在一個籠子里，從上面數(shù)，有35個頭；從下面數(shù)，有94只腳。求籠中各有幾只雞和兔？,《孫子算經(jīng)》,6,我國古代數(shù)學名著《孫子算經(jīng)》中有“物不知數(shù)”的題目： 今有物不知其數(shù)， 三三數(shù)之剩2， 五五數(shù)之剩3， 七七數(shù)之剩2， 問物幾何？,《孫子算經(jīng)》中的題目,這

6、里面又有什么秘密呢？題目給出的條件，也僅僅是作除法時的余數(shù)。,7,問題： 今有物不知其數(shù)，二二數(shù)之剩1，三三數(shù)之剩2，四四數(shù)之剩3，五五數(shù)之剩4，六六數(shù)之剩5，七七數(shù)之剩6，八八數(shù)之剩7，九九數(shù)之剩8，問物幾何？,二、問題的解答,1．先從另一個問題入手,思考：此問題是否比原問題簡單些嗎？,8,再從中挑“用5除余4”的數(shù)，… 一直篩選下去，舍得下功夫，就一定可得結(jié)果。并且看起來，解，還不是唯一的；可能有無窮多個解。,1,3,

7、5,7,9,11,13,15,17,19,21,23,…（用2除余1）5,11,17,23,… （用3除余2）11,23,… （用4除余3）,1）篩法,思考一下：解題的思路是什么？,9,當問題中有很多類似的條件時，我們先只看其中兩三個條件，這就是化繁為簡。 一個復雜的問題，如果在簡化時仍然保留了原來問題的特點和本質(zhì)，那么簡化就“不失一般性”

8、。 學會“簡化問題”與學會“推廣問題”一樣，是一種重要的數(shù)學能力。,化繁為簡的思想,尋找規(guī)律的思想,把我們的解題方法總結(jié)為篩法，是重要的進步，是質(zhì)的飛躍——找到規(guī)律了。 篩法是一般性方法，還可以用來解決其他類似的問題。,10,① 化繁為簡 我們還是先看只有前兩個條件的簡化題目。 1,3,5,7,9,11,13,15,17,19,21,23,25,…（用2除余1） 5,11,17,23,… （用3除余2）

9、 上述篩選過程的第一步，得到: 1,3,5,7,9,11,13,15,17,19,21,23,25,… 其實是列出了“用2除余1”的數(shù)組成的數(shù)列。這個數(shù)列實際上是用帶余除法的式子得到的。,2)公倍數(shù)法,11,對任意給定被除數(shù)a，不為零的除數(shù)b，必唯一存在商q和余數(shù)r，使,,,,,,,所謂“帶余除法”，是指整數(shù)的如下 “除法”：,當余數(shù)r =0時，則 a=bq，稱為 “a被b整除”，或“b整除a”，這是通常除法“

10、 ” 的另一種表達形式。所以，帶余除法是通常除法的推廣。,12,就是“帶余除法”的式子. 當取 時，用上式求得的x正好組成上述數(shù)列 1,3,5,7,9,11,13,15,17,19,21,23,25,…,,,,設這樣的數(shù)為x，則 。這里x是被除數(shù)，2是除數(shù)， 是商，1是余數(shù)，且 。,回到求“用2除余1的數(shù)”的問題。,13,接著從中篩選出“用3除余

11、2”的數(shù)，就是挑出符合下面“帶余除法”表達式的數(shù)，這里 可取0，1，2，3，4，… 再繼續(xù)做下去……..,,,如果我們不分上面兩步，而是一上來就綜合考慮兩者，則就是要解聯(lián)立方程組,14,那么，為了解這個方程組，除了剛才的篩法外，還有沒有更加巧妙的解法？ 我們考察上邊兩個方程的特點，發(fā)現(xiàn)，兩個“帶余除法”的式子，都是“余數(shù)比除數(shù)少1”。 于是想到，如果把被除數(shù)再加1，不是余數(shù)就為0了嗎？換句話說

12、，不是就出現(xiàn)整除的情況了嗎？,于是把上邊每個方程兩邊都加上1，成為,15,這說明， x+1既是2的倍數(shù)，又是3的倍數(shù)，因此，它是2與3的公倍數(shù)。由此想到對整個問題尋找規(guī)律。,,再看問題： 今有物不知其數(shù)，二二數(shù)之剩1，三三數(shù)之剩2，四四數(shù)之剩3，五五數(shù)之剩4，六六數(shù)之剩5，七七數(shù)之剩6，八八數(shù)之剩7，九九數(shù)之剩8，問物幾何？,對整個問題尋找規(guī)律,16,②尋找規(guī)律 設問題中,需要求的數(shù)是x,則被2,3,4,5,6

13、,7,8,9去除，所得的余數(shù)都是比除數(shù)少1，于是我們把被除數(shù)x再加1,則x+1就可被2,3,4,5,6,7,8,9均整除.也就是說，x+1是2,3,4,5,6,7,8,9的公倍數(shù)，從而是其最小公倍數(shù)[2,3,4,5,6,7,8,9]的倍數(shù)。,即 這就是原問題的全部解，有無窮多個解，其中第一個解是2519；我們只取正數(shù)解，因為“物體的個數(shù)”總是正整數(shù)。,17

14、,思考題： ①求“用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,11 除都余2”的數(shù)。,18,2.《孫子算經(jīng)》中“有物不知其數(shù)” 問題的解答,問題：今有物不知其數(shù)， 三三數(shù)之剩2， 五五數(shù)之剩3， 七七數(shù)之剩2，

15、 問物幾何？,19,1）篩法:2,5，8，11，14，17，20，23，26，29，…（用3除余2）8，23，… （用5除余3）23，… （用7除余2）由此得到，23是最小的一個解。至于下一個解是什么，要把“…”寫出來才知道；實踐以后發(fā)現(xiàn)，是要費一點兒功夫的。,20,2）公倍數(shù)法 現(xiàn)在仿照上邊用過的“公倍數(shù)法”，設要求的數(shù)為

16、x ，則依題意，得聯(lián)立方程組,按上一問題中“公倍數(shù)法”解決問題的思路：把方程兩邊同時加上或減去一個什么樣的數(shù)，就能使三個等式的右邊分別是3，5，7的倍數(shù)，從而等式左邊就是3，5，7的公倍數(shù)了。,21,一種試算的方法,從第三個等式入手，兩邊加5（或減2）則得,這要通過反復的試算去完成。,22,則右邊是7的倍數(shù)了，但兩邊加5（或減2）并不能使前兩式的右邊分別是3的倍數(shù)和5的倍數(shù)，所以兩邊加5（或減2）并不能使右邊成為3，5，7的公倍數(shù)。再繼

17、續(xù)從第三個等式入手，為使第三個等式右邊仍然保持是7的倍數(shù)，可再加7l（或再減7l），,（或 ）,,,,最后發(fā)現(xiàn)，為達到目的（三個等式的右邊分別是3,5,7的倍數(shù)）,最小的加數(shù)是82(l=11時,5+7l=82）（或最小的減數(shù)是23，即h=3,2+7h=23）。,將 代入試算、分析，,23,多了一個“ ” ，因這時x也是正數(shù)，合要求。,,,用等式

18、兩邊加82來求解，有,用等式兩邊減23來求解，有,24,這兩組解是一樣的，都是 “23，23+105，23+2×105，……”。 原因是82+23=105，故令 第一組解就成為,,,便轉(zhuǎn)化成第二組解。,但是，這82和23來之不易；并且如果題目中的余數(shù)變了，就得重新試算，所以這方法缺少一般性，為使它具有一般性，要做根本的修改。,25,3）單因子構(gòu)件湊成法,我們先對前幾頁（*）式作兩個方面的

19、簡化:一方面是每次只考慮“一個除式”有余數(shù)的情況(即另兩個除式都是整除的情況):另一方面是把余數(shù)都簡化為最簡單的1。這樣得到三組方程。,26,（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ù)。,,對（1）式而言，這個數(shù)可以取70，對（

20、2）式而言，這個數(shù)可以取21，對（3）式而言，這個數(shù)可以取15。,27,于是（1）式兩邊同減70變?yōu)檫@樣：第二式右邊仍是5的倍數(shù)，第三式右邊仍是7的倍數(shù)，而第一式右邊因為減的70是“用3除余1”的數(shù)，正好原來也多一個1，減沒了。第一式右邊也成為了倍數(shù)，是3的倍數(shù)。,28,,,,（2）式兩邊同減21變?yōu)?（3）式兩邊同減15變?yōu)?29,現(xiàn)在重復一下：所得的x是被3除余1，被5和7除余0的數(shù)；y是被5除余1，被3和7除余0的數(shù)；z是被7除余

21、1，被3和5除余0的數(shù)。,于是得到,那么，湊出s =2x+3y+2z , s不就是我們需要求的數(shù)嗎？,30,因為用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及

22、除3y均余0， 又除z余1 除2z余2， ∴用7除s時余2。,,,,31,于是我們要求的數(shù)是,,,這就是《孫子算經(jīng)》中“物不知其數(shù)” 一題的解，有無窮多解，最小的正整數(shù)解是23（k=-2時）。,32,這里,(1),(2),(3)三式分別叫三個“單子因構(gòu)件”,分別解得,,,每個單因子構(gòu)件,都是用某一個數(shù)去除余1,用另兩個數(shù)去除均余0的情況。再據(jù)題目要求余數(shù)分別是2,3,2的情況,湊成,再看由（*）式得到的下面三個

23、式子：,33,所以，上述方法叫“單因子構(gòu)件湊成法” ——解決“由幾個平行條件表述的問題”的方法 （ 也稱“孫子—華方法”） 這種方法的最大優(yōu)點是，可以任意改變余數(shù)，加以推廣： 問題： 有物不知其數(shù)，三三數(shù)之剩a， 五五數(shù)之剩b，七七數(shù)之剩c，問物幾何？ 答：解為

24、 （ 的選取應使 ）.,,,,34,推廣了的“物不知其數(shù)”問題的解為 明朝數(shù)學家程大位在《算法統(tǒng)宗》中把上式總結(jié)為一首通俗易懂的歌決： 三人同行七十稀，五樹梅花廿一枝， 七子團圓正半月，除百零五便得知。其中正半月是指15,這個口訣把3,5,7;70,21,15及105這幾個關(guān)鍵的數(shù)都總結(jié)在內(nèi)了。詳細說,歌

25、訣的含義是:用3除的余數(shù)乘70,5除的余數(shù)乘21,7除的余數(shù)乘15,相加后再減去（“除”當“減”講）105的適當倍數(shù),就是需要求的（最小）解了。,4）歌訣,35,當然，解，不是唯一的，每差105，都是另一個解答，但如果結(jié)合實際問題，答案往往就是唯一的了。例如一隊士兵的大約人數(shù)，韓信應是知道的。,36,三、中國剩余定理 1247年南宋的數(shù)學家秦九韶把《孫子算經(jīng)》中“物不知其數(shù)”一題的方法推廣到一般的情況，得到稱之為“大衍求一術(shù)”的

26、方法，在《數(shù)書九章》中發(fā)表。這個結(jié)論在歐洲要到十八世紀才由數(shù)學家高斯和歐拉發(fā)現(xiàn)。所以世界公認這個定理是中國人最早發(fā)現(xiàn)的，特別稱之為“中國剩余定理”（Chinese remainder theorem）。,該定理用現(xiàn)在的語言表達如下：,37,設 兩兩互素，設x分別被 除所得的余數(shù)為 ，則x可表示為下式 其中D是 的最小公倍數(shù)； 是

27、 的公倍數(shù)，而且被 除所得余數(shù)為1;k是任意整數(shù)。,,,,,,,,,要注意的是,用上述定理時， 必須兩兩互素.前面的問題中,3,5,7是兩兩互素的,所以“三三數(shù),五五數(shù),七七數(shù)”得余數(shù)后可用此公式。但“四四數(shù),六六數(shù),九九數(shù)”得余數(shù)后就不能用此公式,因為4,6,9并不是兩兩互素的。,38,“中國剩余定理”不僅有光輝的歷史意義，直到現(xiàn)在還是一個非常重要的定理。1970年，年輕的蘇聯(lián)數(shù)學家尤

28、里.馬季亞謝維奇（Матиясевич）（28歲）解決了希爾伯特提出的23個問題中的第10個問題，轟動了世界數(shù)學界。他在解決這個問題時，用到的知識十分廣泛，而在一個關(guān)鍵的地方，就用到了我們的祖先一千多年前發(fā)現(xiàn)的這個“中國剩余定理”。,“中國剩余定理”意義,39,希爾伯特,希爾伯特的第10個問題： 丟番圖方程的可解性 能求出一個整系數(shù)方程的整數(shù)根，稱為丟番圖方程可解。希爾伯特的問題，能否用一種由有限步構(gòu)成的一般算法判斷一個丟番圖

29、方程的可解性？1970年，蘇聯(lián)的IO.B.馬季亞謝維奇證明了希爾伯特所期望的算法不存在。,40,四、有趣的應用 某單位有100把鎖，分別編號為1,2,3,…,100?，F(xiàn)在要對鑰匙編號,使外單位的人看不懂,而本單位的人一看見鎖的號碼就知道該用哪一把鑰匙。,解 把鎖的號碼被3,5,7去除所得的三個余數(shù)來作鑰匙的號碼（首位余數(shù)是0時，也不能省略）。這樣每把鑰匙都有一個三位數(shù)編號。例如23號鎖的鑰匙編號是232號,52號鎖的鑰匙編號是1

30、23號。,8號鎖—231,19號鎖—145,45號鎖—003,52號鎖—123. 因為只有100把鎖,不超過105,所以鎖的編號與鑰匙號是一一對應的。 如果希望保密性再強一點兒,則可以把剛才所說的鑰匙編號加上一個固定的常數(shù)作為新的鑰匙編號系統(tǒng)。甚至可以每過一個月更換一次這個常數(shù)。這樣,仍不破壞鎖的號與鑰匙的號之間的一一對應,而外人則更難知道了。,41,1. 有5個外形相同的乒乓球，其中只有1個重量不標準的次品乒乓球。現(xiàn)再

31、給你一個標準球；請用一架不帶砝碼的天平，最多兩次使用該天平，找出上述次品乒乓球。,2.有12個外形相同的乒乓球，其中只有1個重量不標準的次品乒乓球。請用一架不帶砝碼的天平，最多三次使用該天平，找出上述次品乒乓球，并判斷它是重于標準球，還是輕于標準球。,最優(yōu)化思想,最少次數(shù)完成預定任務最大限度發(fā)揮該天平的作用,請思考:下面的問題如何解決？趣題—找次品：,42,③ 求“用2，3，4，5，6，7，8，9除都余1”的數(shù)。 答：,,,,