韓信點兵與中國剩余定理

1、韓信點兵與中國剩余定理韓信點兵與中國剩余定理 一、一、“韓信點兵韓信點兵”的故事和的故事和孫子孫子 算經(jīng)算經(jīng)中的問題中的問題 1.“韓信點兵韓信點兵”的故事的故事 據(jù)傳，韓信閱兵時，讓一隊士兵據(jù)傳，韓信閱兵時，讓一隊士兵5人一行排隊從他面前走人一行排隊從他面前走 過，他記下最后一行士兵的人數(shù)（過，他記下最后一行士兵的人數(shù)（1人）；再讓這隊士兵人）；再讓這隊士兵6人一人一 行排隊從他面前走過，他記下最后一行士兵的人數(shù)（行排隊從他面前走過，他記下最后一行士兵的人數(shù)（5人）；人）； 再讓這隊士兵再讓這隊士兵7人一行排隊從他面前走過，他記下最后一行士人一行排隊從他面前走過，他記下最后一行士 兵的人數(shù)（

2、兵的人數(shù)（4人），再讓這隊士兵人），再讓這隊士兵11人一行排隊從他面前走過，人一行排隊從他面前走過， 他記下最后一行士兵的人數(shù)（他記下最后一行士兵的人數(shù)（10人）。人）。 然后韓信就憑這些數(shù)，可以求得這隊士兵的總?cè)藬?shù)。然后韓信就憑這些數(shù)，可以求得這隊士兵的總?cè)藬?shù)。 這里面有什么秘密呢？這里面有什么秘密呢？ 韓信好像非常重視作除法時的韓信好像非常重視作除法時的 2.孫子算經(jīng)孫子算經(jīng)中的問題中的問題 我國古代數(shù)學名著我國古代數(shù)學名著孫子算經(jīng)孫子算經(jīng)中有中有“物不知數(shù)物不知數(shù)”的問題：的問題： 今有物不知其數(shù)，今有物不知其數(shù)， 三三數(shù)之剩三三數(shù)之剩2， 五五數(shù)之剩五五數(shù)之剩3， 七七數(shù)之剩七七數(shù)之剩

3、2， 問物幾何？問物幾何？ 這里面又有什么秘密呢？這里面又有什么秘密呢？ 問題給出的條件，問題給出的條件， 也僅僅是作除法時的也僅僅是作除法時的余數(shù)余數(shù) 孫子算經(jīng)孫子算經(jīng) 二問題的解答二問題的解答 1從另一個問題入手從另一個問題入手 問題：問題：今有物不知其數(shù)，二二數(shù)之剩今有物不知其數(shù)，二二數(shù)之剩1，三，三 三數(shù)之剩三數(shù)之剩2，四四數(shù)之剩，四四數(shù)之剩3，五五數(shù)之剩，五五數(shù)之剩4，六六，六六 數(shù)之剩數(shù)之剩5，七七數(shù)之剩，七七數(shù)之剩6，八八數(shù)之剩，八八數(shù)之剩7，九九數(shù)，九九數(shù) 之剩之剩8，問物幾何？，問物幾何？ 1）篩法）篩法 1，3，5，7，9，11，13，15，17，19， 21，23， （

4、用用2除余除余1） 5， 11， 17， 23， （ 用用3除余除余2） 11， 23， （ 用用4除余除余3） 再從中挑再從中挑“用用5除余除余4”的數(shù)，的數(shù)，“用用6除余除余5的數(shù)的數(shù)”， 一直篩選下去，舍得下功夫，就一定可得結(jié)果。一直篩選下去，舍得下功夫，就一定可得結(jié)果。 并且看起來，解，還不是唯一的；可能有無窮并且看起來，解，還不是唯一的；可能有無窮 多個解。多個解。 化繁為簡的思想化繁為簡的思想 當問題中有很多類似的條件時，我們先只看其中兩三個條件，這就當問題中有很多類似的條件時，我們先只看其中兩三個條件，這就 是是化繁為簡化繁為簡。 一個復雜的問題，如果在簡化時仍然一個復雜的問題，

5、如果在簡化時仍然保留了原來問題的特點和本質(zhì)保留了原來問題的特點和本質(zhì)， 那么簡化就那么簡化就“不失一般性不失一般性”。 學會學會“簡化問題簡化問題”與學會與學會“推廣問題推廣問題”一樣，是一種重要的數(shù)學能一樣，是一種重要的數(shù)學能 力。力。 尋找規(guī)律的思想尋找規(guī)律的思想 把我們的解題方法總結(jié)為把我們的解題方法總結(jié)為篩法篩法，是重要的進步，是質(zhì)的飛躍：，是重要的進步，是質(zhì)的飛躍： 找到規(guī)律了。找到規(guī)律了。 篩法是一般性方法，還可以用來解決其他類似的問題。篩法是一般性方法，還可以用來解決其他類似的問題。 2）公倍數(shù)法）公倍數(shù)法 化繁為簡化繁為簡 我們還是先看只有前兩個條件的簡化題目。我們還是先看只有

6、前兩個條件的簡化題目。 1，3，5，7，9，11，13，15，17，19，21，23，25， （ 用用2除余除余1） 5， 11， 17， 23， （ 用用3除余除余2） 上述篩選過程的第一步，得到上述篩選過程的第一步，得到: : 1 1，3 3，5 5，7 7，9 9，1111，1313，1515，1717，1919，2121，2323，2525， 其實是列出了其實是列出了“用用2 2除余除余1”1”的數(shù)組成的數(shù)列。這個數(shù)列的數(shù)組成的數(shù)列。這個數(shù)列 實際上是用實際上是用帶余除法帶余除法的式子得到的。的式子得到的。 所謂所謂“帶余除法帶余除法”，是指，是指整數(shù)整數(shù)的如的如 下下 “除法除法”：

7、 被除數(shù)被除數(shù) ，除數(shù)，除數(shù) , 必唯一必唯一 存在商存在商 和余和余 ，使，使 q ,0abqrrb 0b a r 當余當余 時，則時，則 ，稱為，稱為 “ 整除整除”，或，或 “ 整除整除 ”，這是通常除，這是通常除 法法 “ ” 的另一種表達形式。所以，的另一種表達形式。所以， 帶余帶余 除法是通常除法的推廣。除法是通常除法的推廣。 0r abq ab被 b a a q b 回到求回到求“用用2除余除余1的數(shù)的數(shù)”的問題。設的問題。設 這這 樣的數(shù)為樣的數(shù)為 ，則，則 。這里。這里 是是 被除數(shù)，被除數(shù)，2是除數(shù)，是除數(shù)， 是商，是商，1是余數(shù)，是余數(shù)， 且且 。 x 1 21xnx 0

8、12 1 n 這就是這就是“帶余除帶余除 法法”的式子。當取的式子。當取 時，時， 用上式求得的用上式求得的 正好組成上述數(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 接著從中篩選出接著從中篩選出“用用3除余除余2”的的 數(shù)，就是挑出符合下面數(shù)，就是挑出符合下面“帶余除法帶余除法”表達表達 式式 的數(shù)，這里的數(shù)，這里 可取可取0，1，2，3，4， 再繼續(xù)做下去。再繼續(xù)做下去。 2 32,(023)xn 2 n 如果我們不分上面兩步，而是一上如果我們不分上面兩步，而是一上 來就來就綜合綜合考

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

10、程兩邊都加上于是把上邊每個方程兩邊都加上1，成為，成為 這說明，這說明， 既是既是2的倍數(shù)，又是的倍數(shù)，又是3的的 倍數(shù)，因此，它是倍數(shù)，因此，它是2與與3的公倍數(shù)。由此想到的公倍數(shù)。由此想到 1 2 12(1) 13(1) xn xn 1x 對整個問題尋找規(guī)律對整個問題尋找規(guī)律 問題：問題： 今有物不知其數(shù)，二二數(shù)之剩今有物不知其數(shù)，二二數(shù)之剩1，三，三 三數(shù)之剩三數(shù)之剩2，四四數(shù)之剩，四四數(shù)之剩3，五五數(shù)之剩，五五數(shù)之剩4， 六六數(shù)之剩六六數(shù)之剩5，七七數(shù)之剩，七七數(shù)之剩6，八八數(shù)之剩，八八數(shù)之剩7， 九九數(shù)之剩九九數(shù)之剩8，問物幾何？，問物幾何？ 尋找規(guī)律尋找規(guī)律 設問題中，需要求的數(shù)是

11、設問題中，需要求的數(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 即即 這就是原問題的全部解，有無窮多個解，其中第這就是原問題的全部解，有無窮多個解，其中第 一個解是一個解是2519；我們只取正數(shù)解，因為；我們只取正數(shù)解，因為“物

12、體的物體的 個數(shù)個數(shù)”總是正整數(shù)或總是正整數(shù)或0。 12,3,4,5,6,7,8,92520,1,2,3,xkkk 25201,1,2,3,xkk 思思： 求求“用用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，5，6，7，8，9除除 都都 余余1”的數(shù)。的數(shù)。 求求“用用5，7，9，11 除都余除都余2”的數(shù)。的數(shù)。 2孫子算經(jīng)孫子算經(jīng)中中“有物不知其數(shù)有物不知其數(shù)” 問題的解答問題的解答 問題：問

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

14、求的數(shù)為設要求的數(shù)為 ，則依題意，得聯(lián)立，則依題意，得聯(lián)立 方程組方程組 x 1 2 3 32 53(*) 72 xn xn xn 按上一問題中按上一問題中“公倍數(shù)法公倍數(shù)法”解決問題的解決問題的 思路：把思路：把方程兩邊同時加上或減去方程兩邊同時加上或減去一個什么一個什么 樣的數(shù)，就能使三個等式的右邊分別是樣的數(shù)，就能使三個等式的右邊分別是3 3，5 5， 7 7的倍數(shù)，從而等式左邊就是的倍數(shù)，從而等式左邊就是3 3，5 5，7 7的公倍的公倍 數(shù)了。數(shù)了。 這要通過這要通過反復反復的試算去完成。的試算去完成。 一種試算的方法一種試算的方法 1 2 3 32 53(*) 72 xn xn x

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

16、分 析，析， 7l 3 577(1)xlnl 3 277()xhnh 1,2,3l 7h (1,2,3)h 或 最后發(fā)現(xiàn)，為達到目的最后發(fā)現(xiàn)，為達到目的 （三個等式的右邊分別是（三個等式的右邊分別是3，5，7的倍的倍 數(shù)），最小的加數(shù)是數(shù)），最小的加數(shù)是82（ 時時 ）（或最小的減數(shù)是（或最小的減數(shù)是23， 即即 時時 ）。 11l 5782l 3h 2723h 用等式兩邊加用等式兩邊加82來求解，有來求解，有 用等式兩邊減用等式兩邊減23來求解，有來求解，有 多了一個多了一個“ ” ，因這時，因這時 也是正數(shù)，合也是正數(shù)，合 要求要求。 0k 1 2 3 823(28) 825(17)823

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

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

19、(1);51(2);5(3) 7771 xnynzn xnynzn xnynzn （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 xnynzn xnynzn xnynzn 對（對（1）式而言，

20、這個數(shù)可以?。┦蕉?，這個數(shù)可以取70，對（，對（2）式而言，）式而言， 這個數(shù)可以取這個數(shù)可以取21，對（，對（3）式而言，這個數(shù)可以?。┦蕉?，這個數(shù)可以取15。 于是（于是（1）式兩邊同減）式兩邊同減70變?yōu)檫@樣：變?yōu)檫@樣：第二式右邊仍是第二式右邊仍是5的的 倍數(shù)，第三式右邊仍是倍數(shù)，第三式右邊仍是7的倍數(shù)，而第一式右邊因為減的的倍數(shù)，而第一式右邊因為減的70 是是“用用3除余除余1”的數(shù)，正好原來也多一個的數(shù)，正好原來也多一個1，減沒了。第一，減沒了。第一 式右邊也成為了倍數(shù)，是式右邊也成為了倍數(shù)，是3的倍數(shù)。的倍數(shù)。 111 222 333 3133 5(1);51 (2);5(3)

21、 7771 xnynzn xnynzn xnynzn （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 （3）式兩邊同減）式兩邊同減15變?yōu)樽優(yōu)?于是得到于是得到 133 233 2 153(5)153,5,7105 155(3)10515,0,1,2, 157(2) znzkk znzkk zn 1 2 3 10570 105

22、21 10515 xk yk zk 現(xiàn)在重復一下：所得的現(xiàn)在重復一下：所得的x是是被被3除余除余1， 被被5和和7除余除余0的數(shù)；的數(shù)；y是是被被5除余除余1，被，被3和和7 除余除余0的數(shù)；的數(shù)；z是是被被7除余除余1，被，被3和和5除余除余0的的 數(shù)。數(shù)。 那么，湊出那么，湊出 ， s 不就是我們需要求的數(shù)嗎？不就是我們需要求的數(shù)嗎？ 232sxyz 因為，用因為，用3去除去除s時，除時，除y及除及除z均余均余0 除除3y及除及除2z均余均余0， 又除又除x余余1 除除2x余余2，用用3除除s時余時余2。 用用5去除去除s時，除時，除x及除及除z均余均余0 除除2x及除及除2z均余均余0，

23、 又除又除y余余1 除除3y余余3，用用5除除s時余時余3。 用用7去除去除s時，除時，除x及除及除y均余均余0 除除2x及除及除3y均余均余0， 又除又除z余余1 除除2z余余2， 用用7除除s時余時余2。 于是我們要求的數(shù)是于是我們要求的數(shù)是 這就是這就是孫子算經(jīng)孫子算經(jīng)中中“物不知其數(shù)物不知其數(shù)” 一題的解，有無窮多解，最小的正整數(shù)解是一題的解，有無窮多解，最小的正整數(shù)解是 23（ 時）。時）。 123 123 232 2(10570)3(10521)2(10515) (70221 3152)105(232) 70221 31521052, 1,0,1,2,3, sxyz kkk kkk

24、 kk 2k 這里，（這里，（1），（），（2），（），（3）三式分別叫三個）三式分別叫三個“單子因構(gòu)件單子因構(gòu)件”， 分別解得分別解得 每個單因子構(gòu)件，都是用某一個數(shù)去除余每個單因子構(gòu)件，都是用某一個數(shù)去除余1，用另兩個數(shù)去除均，用另兩個數(shù)去除均 余余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 所以，上述方法叫所以，上述方法叫“單因子構(gòu)件湊成

25、法單因子構(gòu)件湊成法” 解決解決“由幾個平行條件表述的問題由幾個平行條件表述的問題”的方法的方法 （ 也稱也稱“孫子孫子華方法華方法”） 這種方法的最大優(yōu)點是，可以這種方法的最大優(yōu)點是，可以任意改變余數(shù)任意改變余數(shù)，以加以，以加以 推廣推廣： 問問題：有物不知其數(shù)，三三數(shù)之剩題：有物不知其數(shù)，三三數(shù)之剩a，五五數(shù)，五五數(shù) 之剩之剩b，七七數(shù)之剩，七七數(shù)之剩c，問物幾何？，問物幾何？ 答：答：解為解為 （ 的選取應使的選取應使 ）. 702115105sabck ,kkz0s 4）歌訣）歌訣 推廣了的推廣了的“物不知其數(shù)物不知其數(shù)”問題的解為問題的解為 明朝數(shù)學家程大位在明朝數(shù)學家程大位在算法統(tǒng)宗

26、算法統(tǒng)宗中把上式總結(jié)為一中把上式總結(jié)為一 首通俗易懂的歌決：首通俗易懂的歌決： 三人同行七十稀，五樹梅花廿一枝，三人同行七十稀，五樹梅花廿一枝， 七子團圓正半月，除百零五便得知。七子團圓正半月，除百零五便得知。 其中正半月是指其中正半月是指15，這個口訣把，這個口訣把3，5，7；70，21， 15及及105這幾個關(guān)鍵的數(shù)都總結(jié)在內(nèi)了。詳細說，歌訣的這幾個關(guān)鍵的數(shù)都總結(jié)在內(nèi)了。詳細說，歌訣的 含義是：用含義是：用3除的余數(shù)乘除的余數(shù)乘70，5除的余數(shù)乘除的余數(shù)乘21，7除的余數(shù)除的余數(shù) 乘乘15，相加后再減去（，相加后再減去（“除除”當當“減減”講）講）105的適當倍的適當倍 數(shù)，就是需要求的（

27、最?。┙饬?。數(shù)，就是需要求的（最?。┙饬恕?702115105sabck 當然，解不是唯一的，每差當然，解不是唯一的，每差105， 都是另一個解答，但如果結(jié)合實際問題，都是另一個解答，但如果結(jié)合實際問題， 答案往往就是唯一的了。例如一隊士兵的答案往往就是唯一的了。例如一隊士兵的 大約人數(shù)，韓信應是知道的。大約人數(shù)，韓信應是知道的。 三、中國剩余定理三、中國剩余定理 1247年南宋的數(shù)學家秦九韶把年南宋的數(shù)學家秦九韶把孫子算經(jīng)孫子算經(jīng) 中中“物不知其數(shù)物不知其數(shù)”一題的方法推廣到一般的情況，一題的方法推廣到一般的情況， 得到稱之為得到稱之為“大衍求一術(shù)大衍求一術(shù)”的方法，在的方法，在數(shù)書九章數(shù)書

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

29、為余數(shù)為1； 是任意整數(shù)。是任意整數(shù)。 i d 12 , n d dd 12 , n d dd 12 , n r rr 1122nn xkrkrkrkd 12 , n d dd i k 111 , iin dddd d k x x 要注意的是，用上述定理時，要注意的是，用上述定理時， 必須兩兩互素。前面的問題中，必須兩兩互素。前面的問題中，3，5，7是兩是兩 兩互素的，所以兩互素的，所以“三三數(shù)，五五數(shù)，七七數(shù)三三數(shù)，五五數(shù)，七七數(shù)”得得 余數(shù)后可用此公式。但余數(shù)后可用此公式。但“四四數(shù)，六六數(shù)，九四四數(shù)，六六數(shù)，九 九數(shù)九數(shù)”得余數(shù)后就不能用此公式，因為得余數(shù)后就不能用此公式，因為4、6、9 并不是兩兩互素的。并不是兩兩互素的。 12 , n d dd “中國剩余定理中國剩余定理”不僅有光輝的歷史意義，直到現(xiàn)在不僅有光輝的歷史意義，直到現(xiàn)在 還是一個非常重要的定理。還是一個非常重要的定理。1970年，年輕的蘇聯(lián)數(shù)學家年，年輕的蘇聯(lián)數(shù)學家 尤里尤里. .馬季亞謝維奇（）（）（28歲）解決了希歲）解決