韓信點(diǎn)兵與中國剩余定理PPT參考課件

1、2021/3/10授課：XXX1 第五節(jié)韓信點(diǎn)兵與中國剩余定理第五節(jié)韓信點(diǎn)兵與中國剩余定理 2021/3/10授課：XXX2 一、一、“韓信點(diǎn)兵韓信點(diǎn)兵”的故事和的故事和孫子算經(jīng)孫子算經(jīng) 中的題目中的題目 1.“韓信點(diǎn)兵韓信點(diǎn)兵”的故事的故事 韓信閱兵時(shí)，讓一隊(duì)士兵韓信閱兵時(shí)，讓一隊(duì)士兵5人一行排隊(duì)從他面前走人一行排隊(duì)從他面前走 過，他記下最后一行士兵的人數(shù)（過，他記下最后一行士兵的人數(shù)（1人）；再讓這隊(duì)士兵人）；再讓這隊(duì)士兵6 人一行排隊(duì)從他面前走過，他記下最后一行士兵的人數(shù)人一行排隊(duì)從他面前走過，他記下最后一行士兵的人數(shù) （5人）；再讓這隊(duì)士兵人）；再讓這隊(duì)士兵7人一行排隊(duì)從他面前走過，他

2、記人一行排隊(duì)從他面前走過，他記 下最后一行士兵的人數(shù)（下最后一行士兵的人數(shù)（4人），再讓這隊(duì)士兵人），再讓這隊(duì)士兵11人一行人一行 排隊(duì)從他面前走過，他記下最后一行士兵的人數(shù)（排隊(duì)從他面前走過，他記下最后一行士兵的人數(shù)（10人）。人）。 然后韓信就憑這些數(shù)，可以求得這隊(duì)士兵的總?cè)藬?shù)。然后韓信就憑這些數(shù)，可以求得這隊(duì)士兵的總?cè)藬?shù)。 2021/3/10授課：XXX3 這里面有什么秘密呢？這里面有什么秘密呢？ 韓信好像非常重視作除法時(shí)的韓信好像非常重視作除法時(shí)的余數(shù)余數(shù) 2021/3/10授課：XXX4 2.孫子算經(jīng)孫子算經(jīng)中的題目中的題目 我國古代數(shù)學(xué)名著我國古代數(shù)學(xué)名著孫子算經(jīng)孫子算經(jīng)中有中有“

3、物不知數(shù)物不知數(shù)” 的的 題目：題目： 今有物不知其數(shù)，今有物不知其數(shù)， 三三數(shù)之剩三三數(shù)之剩2， 五五數(shù)之剩五五數(shù)之剩3， 七七數(shù)之剩七七數(shù)之剩2， 問物幾何？問物幾何？ 2021/3/10授課：XXX5 這里面又有什么秘密呢？這里面又有什么秘密呢？ 題目給出的條件，題目給出的條件， 也僅僅是作除法時(shí)的也僅僅是作除法時(shí)的余數(shù)余數(shù) 2021/3/10授課：XXX6 孫子算經(jīng)孫子算經(jīng) 2021/3/10授課：XXX7 二問題的解答二問題的解答 1從另一個(gè)問題入手從另一個(gè)問題入手 問題：?jiǎn)栴}：今有物不知其數(shù)，二二數(shù)之剩今有物不知其數(shù)，二二數(shù)之剩1，三三，三三 數(shù)之剩數(shù)之剩2，四四數(shù)之剩，四四數(shù)之剩

4、3，五五數(shù)之剩，五五數(shù)之剩4，六六數(shù)，六六數(shù) 之剩之剩5，七七數(shù)之剩，七七數(shù)之剩6，八八數(shù)之剩，八八數(shù)之剩7，九九數(shù)之，九九數(shù)之 剩剩8，問物幾何？，問物幾何？ 2021/3/10授課：XXX8 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/3/10授課：XXX9 再從中挑再從中挑“用用5除余除余4”的數(shù)，的數(shù)， 一直篩選下去，舍得下功夫，就一定可一直篩選下去，舍得下功夫，就一定可 得結(jié)果。得結(jié)果。 并且看起來，解，還不是唯一

5、的；可能并且看起來，解，還不是唯一的；可能 有無窮多個(gè)解。有無窮多個(gè)解。 2021/3/10授課：XXX10 化繁為簡(jiǎn)化繁為簡(jiǎn)的思想的思想 當(dāng)問題中有很多類似的條件時(shí)，我們先只看其中兩三個(gè)條件，這當(dāng)問題中有很多類似的條件時(shí)，我們先只看其中兩三個(gè)條件，這 就是就是化繁為簡(jiǎn)化繁為簡(jiǎn)。 一個(gè)復(fù)雜的問題，如果在簡(jiǎn)化時(shí)仍然一個(gè)復(fù)雜的問題，如果在簡(jiǎn)化時(shí)仍然保留了原來問題的特點(diǎn)和本保留了原來問題的特點(diǎn)和本 質(zhì)質(zhì)，那么簡(jiǎn)化就，那么簡(jiǎn)化就“不失一般性不失一般性”。 學(xué)會(huì)學(xué)會(huì)“簡(jiǎn)化問題簡(jiǎn)化問題”與學(xué)會(huì)與學(xué)會(huì)“推廣問題推廣問題”一樣，是一種重要的數(shù)學(xué)一樣，是一種重要的數(shù)學(xué) 能力。能力。 尋找規(guī)律尋找規(guī)律的思想的思想

6、 把我們的解題方法總結(jié)為把我們的解題方法總結(jié)為篩法篩法，是重要的進(jìn)步，是質(zhì)的飛躍：，是重要的進(jìn)步，是質(zhì)的飛躍： 找到規(guī)律了。找到規(guī)律了。 篩法是一般性方法，還可以用來解決其他類似的問題。篩法是一般性方法，還可以用來解決其他類似的問題。 2021/3/10授課：XXX11 2 2）公倍數(shù)法）公倍數(shù)法 化繁為簡(jiǎn)化繁為簡(jiǎn) 我們還是先看只有前兩個(gè)條件的簡(jiǎn)化題目。我們還是先看只有前兩個(gè)條件的簡(jiǎn)化題目。 1，3，5，7，9，11，13，15，17，19，21，23，25， （ 用用2除余除余1） 5， 11， 17， 23， （ 用用3除余除余2） 上述篩選過程的第一步，得到上述篩選過程的第一步，得到:

7、: 1 1，3 3，5 5，7 7，9 9，1111，1313，1515，1717，1919，2121，2323，2525， 其實(shí)是列出了其實(shí)是列出了“用用2 2除余除余1”1”的數(shù)組成的數(shù)列。這個(gè)數(shù)列的數(shù)組成的數(shù)列。這個(gè)數(shù)列 實(shí)際上是用實(shí)際上是用帶余除法帶余除法的式子得到的。的式子得到的。 2021/3/10授課：XXX12 所謂所謂“帶余除法帶余除法”，是指，是指整數(shù)整數(shù)的如的如 下下 “除法除法”： 被除數(shù)被除數(shù) ，除數(shù)，除數(shù) , 必唯一必唯一 存在商存在商 和余和余 ，使，使 q ,0abqrrb 0b a r 2021/3/10授課：XXX13 當(dāng)余當(dāng)余 時(shí)，則時(shí)，則 ，稱為，稱為

8、“ 整除整除”，或，或 “ 整除整除 ”，這是通常除，這是通常除 法法“ ” 的另一種表達(dá)形式。所以，的另一種表達(dá)形式。所以， 帶余帶余 除法是通常除法的推廣。除法是通常除法的推廣。 0r abq ab被 b a a q b 2021/3/10授課：XXX14 回到求回到求“用用2除余除余1的數(shù)的數(shù)”的問題。設(shè)的問題。設(shè) 這這 樣的數(shù)為樣的數(shù)為 ，則，則 。這里。這里 是是 被除數(shù)，被除數(shù)，2是除數(shù)，是除數(shù)， 是商，是商，1是余，是余， 且且 。 x 1 21xnx 012 1 n 2021/3/10授課：XXX15 這就是這就是“帶余除帶余除 法法”的式子。當(dāng)取的式子。當(dāng)取 時(shí)，時(shí)， 用上式

9、求得的用上式求得的 正好組成上述數(shù)列正好組成上述數(shù)列 1，3，5，7，9，11，13，15， 17，19，21，23，25， 1 21(012),xn 1 0,1,2,3,4,n x 2021/3/10授課：XXX16 接著從中篩選出接著從中篩選出“用用3除余除余2”的的 數(shù)，就是挑出符合下面數(shù)，就是挑出符合下面“帶余除法帶余除法”表達(dá)表達(dá) 式式 的數(shù)，這里的數(shù)，這里 可取可取0，1，2，3，4， 再繼續(xù)做下去。再繼續(xù)做下去。 2 32,(023)xn 2 n 2021/3/10授課：XXX17 如果我們不分上面兩步，而是一上如果我們不分上面兩步，而是一上 來就來就綜合綜合考慮考慮兩者兩者，則

10、就是要解聯(lián)立方，則就是要解聯(lián)立方 程組程組 1 2 21 . 32 xn x xn 中的 2021/3/10授課：XXX18 那么，為了解這個(gè)方程組，除了剛才的篩法那么，為了解這個(gè)方程組，除了剛才的篩法 外，還有沒有更加巧妙的解法？外，還有沒有更加巧妙的解法？ 我們考察上邊兩個(gè)方程的特點(diǎn)，發(fā)現(xiàn)，兩個(gè)我們考察上邊兩個(gè)方程的特點(diǎn)，發(fā)現(xiàn)，兩個(gè) “帶余除法帶余除法”的式子，都是的式子，都是“余數(shù)比除數(shù)少余數(shù)比除數(shù)少1 1”。 于是想到，如果于是想到，如果把被除數(shù)再加把被除數(shù)再加1 1，不是余數(shù)就，不是余數(shù)就 為為0 0了嗎？換句話說，不是就出現(xiàn)了嗎？換句話說，不是就出現(xiàn)整除整除的情況了嗎？的情況了嗎？

11、 2021/3/10授課：XXX19 于是把上邊每個(gè)方程兩邊都加上于是把上邊每個(gè)方程兩邊都加上1，成為，成為 這說明，這說明， 既是既是2的倍數(shù)，又是的倍數(shù)，又是3的的 倍數(shù)，因此，它是倍數(shù)，因此，它是2與與3的公倍數(shù)。由此想到的公倍數(shù)。由此想到 1 2 12(1) 13(1) xn xn 1x 2021/3/10授課：XXX20 對(duì)整個(gè)問題尋找規(guī)律對(duì)整個(gè)問題尋找規(guī)律 問題：?jiǎn)栴}： 今有物不知其數(shù)，二二數(shù)之剩今有物不知其數(shù)，二二數(shù)之剩1，三三，三三 數(shù)之剩數(shù)之剩2，四四數(shù)之剩，四四數(shù)之剩3，五五數(shù)之剩，五五數(shù)之剩4，六六，六六 數(shù)之剩數(shù)之剩5，七七數(shù)之剩，七七數(shù)之剩6，八八數(shù)之剩，八八數(shù)之剩7

12、，九九，九九 數(shù)之剩數(shù)之剩8，問物幾何？，問物幾何？ 2021/3/10授課：XXX21 尋找規(guī)律尋找規(guī)律 設(shè)問題中，需要求的數(shù)是設(shè)問題中，需要求的數(shù)是 ，則，則 被被2， 3，4，5，6，7，8，9去除，所得的余數(shù)都去除，所得的余數(shù)都 是比除數(shù)少是比除數(shù)少1，于是我們把被除數(shù)，于是我們把被除數(shù) 再加再加1， 則則 就可被就可被2，3，4，5，6，7，8，9均均 整除。也就是說，整除。也就是說， 是是2,3,4,5,6,7,8,9 的公倍數(shù)，從而是其最小公倍數(shù)的公倍數(shù)，從而是其最小公倍數(shù) 2,3,4,5,6,7,8,9的倍數(shù)。的倍數(shù)。 x xx 1x 1x x 2021/3/10授課：XXX2

13、2 即即 這就是原問題的全部解，有無窮多個(gè)解，其中第這就是原問題的全部解，有無窮多個(gè)解，其中第 一個(gè)解是一個(gè)解是2519；我們只取正數(shù)解，因?yàn)?；我們只取正?shù)解，因?yàn)椤拔矬w的物體的 個(gè)數(shù)個(gè)數(shù)”總是正整數(shù)。總是正整數(shù)。 12,3,4,5,6,7,8,92520,1,2,3,xkkk 25201,1,2,3,xkk 2021/3/10授課：XXX23 思思： 求求“用用2除余除余1，3除余除余2， 用用m除余除余 m 1”的數(shù)。的數(shù)。 求求“用用a除余除余a 1，用，用b除余除余b1，用，用c 除余除余c1”的數(shù)。的數(shù)。 （a,b,c是任意大于是任意大于1的自然數(shù)）的自然數(shù)） 求求“用用2，3，4，

14、5，6，7，8，9除除 都都 余余1”的數(shù)。的數(shù)。 求求“用用5，7，9，11 除都余除都余2”的數(shù)。的數(shù)。 2021/3/10授課：XXX24 2孫子算經(jīng)孫子算經(jīng)中中“有物不知其數(shù)有物不知其數(shù)” 問題的解答問題的解答 問題：?jiǎn)栴}：今有物不知其數(shù)，今有物不知其數(shù)， 三三數(shù)之剩三三數(shù)之剩2， 五五數(shù)之剩五五數(shù)之剩3， 七七數(shù)之剩七七數(shù)之剩2， 問物幾何？問物幾何？ 2021/3/10授課：XXX25 1）篩法）篩法. 2，5，8，11，14，17，20，23，26，29，（用（用3除余除余2） 8，23， （用（用5除余除余3） 23， （用（用7除余除余2） 由此得到，由此得到，23是最小的一

15、個(gè)解。是最小的一個(gè)解。 至于下一個(gè)解是什么，要把至于下一個(gè)解是什么，要把“”寫出來才知道；寫出來才知道； 實(shí)踐以后發(fā)現(xiàn)，是要費(fèi)一點(diǎn)兒功夫的。實(shí)踐以后發(fā)現(xiàn)，是要費(fèi)一點(diǎn)兒功夫的。 2021/3/10授課：XXX26 2）公倍數(shù)法）公倍數(shù)法 現(xiàn)在仿照上邊用過的現(xiàn)在仿照上邊用過的“公倍數(shù)法公倍數(shù)法”， 設(shè)要求的數(shù)為設(shè)要求的數(shù)為 ，則依題意，得聯(lián)立，則依題意，得聯(lián)立 方程組方程組 x 1 2 3 32 53(*) 72 xn xn xn 2021/3/10授課：XXX27 按上一問題中按上一問題中“公倍數(shù)法公倍數(shù)法”解決問題的解決問題的 思路：把思路：把方程兩邊同時(shí)加上或減去方程兩邊同時(shí)加上或減去一個(gè)什

16、么一個(gè)什么 樣的數(shù)，就能使三個(gè)等式的右邊分別是樣的數(shù)，就能使三個(gè)等式的右邊分別是3 3，5 5， 7 7的倍數(shù)，從而等式左邊就是的倍數(shù)，從而等式左邊就是3 3，5 5，7 7的公倍的公倍 數(shù)了。數(shù)了。 這要通過這要通過反復(fù)反復(fù)的試算去完成。的試算去完成。 2021/3/10授課：XXX28 一種試算的方法一種試算的方法 1 2 3 32 53(*) 72 xn xn xn 2021/3/10授課：XXX29 從第三個(gè)等式入手，兩邊加從第三個(gè)等式入手，兩邊加5（或減（或減2）則則 得得 3 57(1)xn 3 (27)xn或 2021/3/10授課：XXX30 則右邊是則右邊是7的倍數(shù)了，但兩邊

17、加的倍數(shù)了，但兩邊加5（或減（或減2）并不并不 能使前兩式的右邊分別是能使前兩式的右邊分別是3的倍數(shù)和的倍數(shù)和5的倍數(shù)，所以的倍數(shù)，所以 兩邊加兩邊加5（或減（或減2）并不能使右邊成為并不能使右邊成為3，5，7的公的公 倍數(shù)。再繼續(xù)從第三個(gè)等式入手，為使第三個(gè)等式倍數(shù)。再繼續(xù)從第三個(gè)等式入手，為使第三個(gè)等式 右邊仍然保持是右邊仍然保持是7的倍數(shù)，可再加的倍數(shù)，可再加 （或再減（或再減 ）， 則則 （或（或 ） 將將 代入試算、分代入試算、分 析，析， 7l 3 577(1)xlnl 3 277()xhnh 1,2,3l 7h (1,2,3)h 或 2021/3/10授課：XXX31 最后發(fā)現(xiàn)，

18、為達(dá)到目的最后發(fā)現(xiàn)，為達(dá)到目的 （三個(gè)等式的右邊分別是（三個(gè)等式的右邊分別是3，5，7的倍的倍 數(shù)），最小的加數(shù)是數(shù)），最小的加數(shù)是82（ 時(shí)時(shí) ）（或最小的減數(shù)是（或最小的減數(shù)是23， 即即 時(shí)時(shí) ）。 11l 5782l 3h 2723h 2021/3/10授課：XXX32 用等式兩邊加用等式兩邊加82來求解，有來求解，有 用等式兩邊減用等式兩邊減23來求解，有來求解，有 多了一個(gè)多了一個(gè)“ ” ，因這時(shí)，因這時(shí) 也是正數(shù)，也是正數(shù)， 合合 要求要求。 0k 1 2 3 823(28) 825(17)823,5,7105 827(12)10582,1,2,3, xn xnxkk xnxkk

19、 1 2 3 233(7) 235(4)233,5,7105 237(3)10523,0,1,2,3, xn xnxkk xnxkk x 2021/3/10授課：XXX33 這兩組解是一樣的，都是這兩組解是一樣的，都是“23，23+105， 23+2105，”。 原因是原因是82+23=105，故令，故令 第一組第一組 解就成為解就成為 便轉(zhuǎn)化成第二組解。便轉(zhuǎn)化成第二組解。 1k k 105(1)821051058210523xkkk 2021/3/10授課：XXX34 但是，這但是，這82和和23來之不易；并且如果來之不易；并且如果 題目中的余數(shù)題目中的余數(shù)變了，就得重新試算，所以變了，就得

20、重新試算，所以 這方法缺少一般性，為使它具有一般性，這方法缺少一般性，為使它具有一般性， 要做根本的修改。要做根本的修改。 2021/3/10授課：XXX35 3）單因子構(gòu)件湊成法）單因子構(gòu)件湊成法 我們先對(duì)前幾頁（我們先對(duì)前幾頁（*）式作兩個(gè)方面的簡(jiǎn)化：）式作兩個(gè)方面的簡(jiǎn)化：一方面一方面是是 每次只考慮每次只考慮“一個(gè)除式一個(gè)除式”有余數(shù)的情況（即另兩個(gè)除式都有余數(shù)的情況（即另兩個(gè)除式都 是整除的情況）；是整除的情況）；另一方面另一方面是把余數(shù)都簡(jiǎn)化為最簡(jiǎn)單的是把余數(shù)都簡(jiǎn)化為最簡(jiǎn)單的1。 這樣得到三組方程。這樣得到三組方程。 1 2 3 32 53(*) 72 xn xn xn 111 22

21、2 333 3133 5(1);51(2);5(3) 7771 xnynzn xnynzn xnynzn 2021/3/10授課：XXX36 （1）式意味著，在）式意味著，在5和和7的公倍數(shù)中（的公倍數(shù)中（35，70， 105，）尋找被）尋找被3除余除余1的數(shù)；的數(shù)； （2）式意味著，在）式意味著，在3和和7的公倍數(shù)中（的公倍數(shù)中（21，42， 63，）尋找被）尋找被5除余除余1的數(shù)；的數(shù)； （3）式意味著，在）式意味著，在3和和5的公倍數(shù)中（的公倍數(shù)中（15，30， 45，）尋找被）尋找被7除余除余1的數(shù)。的數(shù)。 111 222 333 3133 5(1);51(2);5(3) 7771 x

22、nynzn xnynzn xnynzn 2021/3/10授課：XXX37 對(duì)（對(duì)（1）式而言，這個(gè)數(shù)可以取）式而言，這個(gè)數(shù)可以取70，對(duì)（，對(duì)（2）式而言，）式而言， 這個(gè)數(shù)可以取這個(gè)數(shù)可以取21，對(duì)（，對(duì)（3）式而言，這個(gè)數(shù)可以取）式而言，這個(gè)數(shù)可以取15。 于是（于是（1）式兩邊同減）式兩邊同減70變?yōu)檫@樣：變?yōu)檫@樣：第二式右邊仍是第二式右邊仍是5的的 倍數(shù)，第三式右邊仍是倍數(shù)，第三式右邊仍是7的倍數(shù)，而第一式右邊因?yàn)闇p的的倍數(shù)，而第一式右邊因?yàn)闇p的70 是是“用用3除余除余1”的數(shù)，正好原來也多一個(gè)的數(shù)，正好原來也多一個(gè)1，減沒了。第一，減沒了。第一 式右邊也成為了倍數(shù)，是式右邊也成為

23、了倍數(shù)，是3的倍數(shù)。的倍數(shù)。 111 222 333 3133 5(1);51(2);5(3) 7771 xnynzn xnynzn xnynzn 2021/3/10授課：XXX38 （2）式兩邊同減）式兩邊同減21變?yōu)樽優(yōu)?111 211 3 703(23)703,5,7105 705(14)10570,0,1,2, 707(10) xnxkk xnxkk xn 122 222 3 213(7)213,5,7105 215(4)10521,0,1,2, 217(3) ynykk ynykk yn 2021/3/10授課：XXX39 （3）式兩邊同減）式兩邊同減15變?yōu)樽優(yōu)?于是得到于是得到

24、133 233 2 153(5)153,5,7105 155(3)10515,0,1,2, 157(2) znzkk znzkk zn 1 2 3 10570 10521 10515 xk yk zk 2021/3/10授課：XXX40 現(xiàn)在重復(fù)一下：所得的現(xiàn)在重復(fù)一下：所得的x是是被被3除余除余1，被，被 5和和7除余除余0的數(shù)；的數(shù)；y是是被被5除余除余1，被，被3和和7除余除余 0的數(shù)；的數(shù)；z是是被被7除余除余1，被，被3和和5除余除余0的數(shù)。的數(shù)。 2021/3/10授課：XXX41 那么，湊出那么，湊出 ， s 不就是我們需要求的數(shù)嗎？不就是我們需要求的數(shù)嗎？ 232sxyz 20

25、21/3/10授課：XXX42 因?yàn)椋靡驗(yàn)?，?去除去除s時(shí)，除時(shí)，除y及除及除z均余均余0 除除3y及除及除2z均余均余0， 又除又除x余余1 除除2x余余2，用用3除除s時(shí)余時(shí)余2。 用用5去除去除s時(shí)，除時(shí)，除x及除及除z均余均余0 除除2x及除及除2z均余均余0， 又除又除y余余1 除除3y余余3，用用5除除s時(shí)余時(shí)余3。 用用7去除去除s時(shí)，除時(shí)，除x及除及除y均余均余0 除除2x及除及除3y均余均余0， 又除又除z余余1 除除2z余余2， 用用7除除s時(shí)余時(shí)余2。 2021/3/10授課：XXX43 于是我們要求的數(shù)是于是我們要求的數(shù)是 這就是這就是孫子算經(jīng)孫子算經(jīng)中中“物不知其

26、數(shù)物不知其數(shù)” 一題的解，有無窮多解，最小的正整數(shù)解是一題的解，有無窮多解，最小的正整數(shù)解是 23（ 時(shí)）。時(shí)）。 123 123 232 2(10570)3(10521)2(10515) (70221 3152)105(232) 70221 31521052, 1,0,1,2,3, sxyz kkk kkk kk 2k 2021/3/10授課：XXX44 這里，（這里，（1），（），（2），（），（3）三式分別叫三個(gè)）三式分別叫三個(gè)“單子因構(gòu)件單子因構(gòu)件”，分，分 別解得別解得 每個(gè)單因子構(gòu)件，都是用某一個(gè)數(shù)去除余每個(gè)單因子構(gòu)件，都是用某一個(gè)數(shù)去除余1，用另兩個(gè)數(shù)去除均余，用另兩個(gè)數(shù)去除均余

27、0 的情況。再據(jù)題目要求余數(shù)分別是的情況。再據(jù)題目要求余數(shù)分別是2，3，2的情況，湊成的情況，湊成 111 222 333 3133 5(1);51(2);5(3) 7771 xnynzn xnynzn xnynzn 232sxyz 1 2 3 10570 10521 10515 xk yk zk 2021/3/10授課：XXX45 所以，上述方法叫所以，上述方法叫“單因子構(gòu)件湊成法單因子構(gòu)件湊成法” 解決解決“由幾個(gè)平行條件表述的問題由幾個(gè)平行條件表述的問題”的方法的方法 （ 也稱也稱“孫子孫子華方法華方法”） 這種方法的最大優(yōu)點(diǎn)是，可以這種方法的最大優(yōu)點(diǎn)是，可以任意改變余數(shù)任意改變余數(shù)，加

28、，加 以以推廣推廣： 題：題： 有物不知其數(shù)，三三數(shù)之剩有物不知其數(shù)，三三數(shù)之剩a，五五數(shù)，五五數(shù) 之剩之剩b，七七數(shù)之剩，七七數(shù)之剩c，問物幾何？，問物幾何？ 答：答：解為解為 （ 的選取應(yīng)使的選取應(yīng)使 ）. 702115105sabck ,kkZ0s 2021/3/10授課：XXX46 4）歌訣）歌訣 推廣了的推廣了的“物不知其數(shù)物不知其數(shù)”問題的解為問題的解為 明朝數(shù)學(xué)家程大位在明朝數(shù)學(xué)家程大位在算法統(tǒng)宗算法統(tǒng)宗中把上式總結(jié)為一首中把上式總結(jié)為一首 通俗易懂的歌決：通俗易懂的歌決： 三人同行七十稀，五樹梅花廿一枝，三人同行七十稀，五樹梅花廿一枝， 七子團(tuán)圓正半月，除百零五便得知。七子團(tuán)圓

29、正半月，除百零五便得知。 其中正半月是指其中正半月是指15，這個(gè)口訣把，這個(gè)口訣把3，5，7；70，21，15 及及105這幾個(gè)關(guān)鍵的數(shù)都總結(jié)在內(nèi)了。詳細(xì)說，歌訣的含這幾個(gè)關(guān)鍵的數(shù)都總結(jié)在內(nèi)了。詳細(xì)說，歌訣的含 義是：用義是：用3除的余數(shù)乘除的余數(shù)乘70，5除的余數(shù)乘除的余數(shù)乘21，7除的余數(shù)乘除的余數(shù)乘 15，相加后再減去（，相加后再減去（“除除”當(dāng)當(dāng)“減減”講）講）105的適當(dāng)倍數(shù)，的適當(dāng)倍數(shù)， 就是需要求的（最小）解了。就是需要求的（最?。┙饬恕?702115105sabck 2021/3/10授課：XXX47 當(dāng)然，解，不是唯一的，每差當(dāng)然，解，不是唯一的，每差105， 都是另一個(gè)解答

30、，但如果結(jié)合實(shí)際問題，都是另一個(gè)解答，但如果結(jié)合實(shí)際問題， 答案往往就是唯一的了。例如一隊(duì)士兵的答案往往就是唯一的了。例如一隊(duì)士兵的 大約人數(shù)，韓信應(yīng)是知道的。大約人數(shù)，韓信應(yīng)是知道的。 2021/3/10授課：XXX48 三、中國剩余定理三、中國剩余定理 1247年南宋的數(shù)學(xué)家秦九韶把年南宋的數(shù)學(xué)家秦九韶把孫子算經(jīng)孫子算經(jīng)中中 “物不知其數(shù)物不知其數(shù)”一題的方法推廣到一般的情況，得一題的方法推廣到一般的情況，得 到稱之為到稱之為“大衍求一術(shù)大衍求一術(shù)”的方法，在的方法，在數(shù)書九章數(shù)書九章 中發(fā)表。這個(gè)結(jié)論在歐洲要到十八世紀(jì)才由數(shù)學(xué)家中發(fā)表。這個(gè)結(jié)論在歐洲要到十八世紀(jì)才由數(shù)學(xué)家 高斯和歐拉發(fā)現(xiàn)

31、。所以世界公認(rèn)這個(gè)定理是中國人高斯和歐拉發(fā)現(xiàn)。所以世界公認(rèn)這個(gè)定理是中國人 最早發(fā)現(xiàn)的，特別稱之為最早發(fā)現(xiàn)的，特別稱之為“中國剩余定理中國剩余定理” （Chinese remainder theorem）。）。 2021/3/10授課：XXX49 該該定理定理用現(xiàn)在的語言表達(dá)如下：用現(xiàn)在的語言表達(dá)如下： 設(shè)設(shè) 兩兩互素，設(shè)兩兩互素，設(shè) 分別被分別被 除所得的余數(shù)為除所得的余數(shù)為 ，則，則 可表示為下式可表示為下式 其中其中 是是 的最小公倍數(shù)；的最小公倍數(shù)； 是是 的公倍數(shù)，而且被的公倍數(shù)，而且被 除所得除所得 余數(shù)為余數(shù)為1； 是任意整數(shù)。是任意整數(shù)。 i d 12 , n d dd 12

32、, n d dd 12 , n r rr 1122nn xkrkrkrkD 12 , n d dd i k 111 , iin dddd D k x x 2021/3/10授課：XXX50 要注意的是，用上述定理時(shí)，要注意的是，用上述定理時(shí)， 必須兩兩互素。前面的問題中，必須兩兩互素。前面的問題中，3，5，7是兩是兩 兩互素的，所以兩互素的，所以“三三數(shù)，五五數(shù)，七七數(shù)三三數(shù)，五五數(shù)，七七數(shù)”得得 余數(shù)后可用此公式。但余數(shù)后可用此公式。但“四四數(shù)，六六數(shù)，九四四數(shù)，六六數(shù)，九 九數(shù)九數(shù)”得余數(shù)后就不能用此公式，因?yàn)榈糜鄶?shù)后就不能用此公式，因?yàn)?、6、9 并不是兩兩互素的。并不是兩兩互素的。 1

33、2 , n d dd 2021/3/10授課：XXX51 “中國剩余定理中國剩余定理”不僅有光輝的歷史意義，直到現(xiàn)在不僅有光輝的歷史意義，直到現(xiàn)在 還是一個(gè)非常重要的定理。還是一個(gè)非常重要的定理。1970年，年輕的蘇聯(lián)數(shù)學(xué)家年，年輕的蘇聯(lián)數(shù)學(xué)家 尤里尤里. .馬季亞謝維奇（）（）（28歲）解決了希歲）解決了希 爾伯特提出的爾伯特提出的23個(gè)問題中的第個(gè)問題中的第10個(gè)問題，轟動(dòng)了世界數(shù)個(gè)問題，轟動(dòng)了世界數(shù) 學(xué)界。他在解決這個(gè)問題時(shí)，用到的知識(shí)十分廣泛，而學(xué)界。他在解決這個(gè)問題時(shí)，用到的知識(shí)十分廣泛，而 在一個(gè)關(guān)鍵的地方，就用到了我們的祖先一千多年前發(fā)在一個(gè)關(guān)鍵的地方，就用到了我們的祖先一千多年

34、前發(fā) 現(xiàn)的這個(gè)現(xiàn)的這個(gè)“中國剩余定理中國剩余定理”。 2021/3/10授課：XXX52 希爾伯特的第10個(gè)問題： 丟番圖方程的可解性 能求出一個(gè)整系數(shù)方程的 整數(shù)根，稱為丟番圖方程可 解。希爾伯特問，能否用一 種由有限步構(gòu)成的一般算法 判斷一個(gè)丟番圖方程的可解 性？1970年，蘇聯(lián)的IO.B. 馬季亞謝維奇證明了希爾伯 特所期望的算法不存在。 希爾伯特 2021/3/10授課：XXX53 四、有趣的應(yīng)用四、有趣的應(yīng)用 某單位有某單位有100把鎖，分別編號(hào)為把鎖，分別編號(hào)為1，2， 3，100。現(xiàn)在要對(duì)鑰匙編號(hào)，使外單位?，F(xiàn)在要對(duì)鑰匙編號(hào)，使外單位 的人看不懂，而本單位的人一看見鎖的號(hào)碼的人看

35、不懂，而本單位的人一看見鎖的號(hào)碼 就知道該用哪一把鑰匙。就知道該用哪一把鑰匙。 2021/3/10授課：XXX54 能采用的方法很多，其中一種就是利用中國能采用的方法很多，其中一種就是利用中國 剩余定理，把鎖的號(hào)碼被剩余定理，把鎖的號(hào)碼被3，5，7去除所得的三個(gè)去除所得的三個(gè) 余數(shù)來作鑰匙的號(hào)碼（首位余數(shù)是余數(shù)來作鑰匙的號(hào)碼（首位余數(shù)是0時(shí)，也不能省時(shí)，也不能省 略）。略）。 這樣每把鑰匙都有一個(gè)三位數(shù)編號(hào)。這樣每把鑰匙都有一個(gè)三位數(shù)編號(hào)。 例如例如23號(hào)鎖的鑰匙編號(hào)是號(hào)鎖的鑰匙編號(hào)是232號(hào)，號(hào)，52號(hào)鎖的鑰匙號(hào)鎖的鑰匙 編號(hào)是編號(hào)是123號(hào)。號(hào)。 2021/3/10授課：XXX55 8號(hào)鎖

36、號(hào)鎖231 19號(hào)鎖號(hào)鎖145 45號(hào)鎖號(hào)鎖003 52號(hào)鎖號(hào)鎖123 因?yàn)橹挥幸驗(yàn)橹挥?00把鎖，不超過把鎖，不超過105，所以鎖的號(hào)與，所以鎖的號(hào)與 鑰匙的號(hào)是一一對(duì)應(yīng)的。鑰匙的號(hào)是一一對(duì)應(yīng)的。 如果希望保密性再強(qiáng)一點(diǎn)兒，則可以把剛才所如果希望保密性再強(qiáng)一點(diǎn)兒，則可以把剛才所 說的鑰匙編號(hào)加上一個(gè)固定的常數(shù)作為新的鑰匙編說的鑰匙編號(hào)加上一個(gè)固定的常數(shù)作為新的鑰匙編 號(hào)系統(tǒng)。甚至可以每過一個(gè)月更換一次這個(gè)常數(shù)。號(hào)系統(tǒng)。甚至可以每過一個(gè)月更換一次這個(gè)常數(shù)。 這樣，仍不破壞鎖的號(hào)與鑰匙的號(hào)之間的一一對(duì)應(yīng)，這樣，仍不破壞鎖的號(hào)與鑰匙的號(hào)之間的一一對(duì)應(yīng)， 而外人則更難知道了。而外人則更難知道了。 2

37、021/3/10授課：XXX56 趣題找次品找次品： 1）有有5個(gè)外形相同的乒乓球，其中只有個(gè)外形相同的乒乓球，其中只有 1個(gè)重量不標(biāo)準(zhǔn)的次品乒乓球。個(gè)重量不標(biāo)準(zhǔn)的次品乒乓球。 現(xiàn)再給你一個(gè)標(biāo)準(zhǔn)球；請(qǐng)用一架不帶現(xiàn)再給你一個(gè)標(biāo)準(zhǔn)球；請(qǐng)用一架不帶 砝碼的天平，最多兩次使用該天平，找砝碼的天平，最多兩次使用該天平，找 出上述次品乒乓球。出上述次品乒乓球。 2021/3/10授課：XXX57 最優(yōu)化思想最優(yōu)化思想 最少次數(shù)完成預(yù)定任務(wù) 最大限度發(fā)揮該天平的作用 2021/3/10授課：XXX58 思考題思考題 2021/3/10授課：XXX59 趣題找次品找次品： 2）有有12個(gè)外形相同的乒乓球，其中只有個(gè)外形相同的乒乓