中國剩余定理.doc

《中國剩余定理.doc》由會員上傳分享，免費在線閱讀，更多相關(guān)內(nèi)容在行業(yè)資料-天天文庫。

1、中國剩余定理在中國古代勞動人民中，長期流傳著“隔墻算”、“剪管術(shù)”、“秦王暗點兵”等數(shù)學(xué)游戲。有一首“孫子歌”，甚至遠渡重洋，輸入日本：“三人同行七十稀，五樹梅花廿一枝，七子團圓正半月，除百零五便得知。”這些饒有趣味的數(shù)學(xué)游戲，以各種不同形式，介紹世界聞名的“孫子問題”的解法，通俗地反映了中國古代數(shù)學(xué)一項卓越的成就。“孫子問題”在現(xiàn)代數(shù)論中是一個一次同余問題，它最早出現(xiàn)在中國公元四世紀(jì)的數(shù)學(xué)著作《孫子算經(jīng)》中?！秾O子算經(jīng)》卷下“物不知數(shù)”題說：有物不知其數(shù)，三個一數(shù)余二，五個一數(shù)余三，七個一數(shù)又余二，問該物總數(shù)幾何

2、？顯然，這相當(dāng)于求不定方程組N=3x+2,N=5y+3,N=7z+2的正整數(shù)解N，或用現(xiàn)代數(shù)論符號表示，等價干解下列的一次同余組?！秾O子算經(jīng)》所給答案是N=23。由于孫子問題數(shù)據(jù)比較簡單，這個答數(shù)通過試算也可以得到。但是《孫子算經(jīng)》并不是這樣做的?！拔锊恢獢?shù)”題的術(shù)文指出解題的方法多三三數(shù)之，取數(shù)七十，與余數(shù)二相乘；五五數(shù)之，取數(shù)二十一，與余數(shù)三相乘；七七數(shù)之，取數(shù)十五，與余數(shù)二相乘。將諸乘積相加，然后減去一百零五的倍數(shù)。列成算式就是：N=70×2+21×3+15×2－2×105。這里105是模數(shù)3、5、7的最小公

3、倍數(shù)，容易看出，《孫子算經(jīng)》給出的是符合條件的最小正整數(shù)。對于一般余數(shù)的情形，《孫子算經(jīng)》術(shù)文指出，只要把上述算法中的余數(shù)2、3、2分別換成新的余數(shù)就行了。以R1、R2、R3表示這些余數(shù)，那么《孫子算經(jīng)》相當(dāng)于給出公式N=70×R1+21×R2+15×R3－P×105（p是整數(shù)）。孫子算法的關(guān)鍵，在于70、21和15這三個數(shù)的確定。后來流傳的《孫子歌》中所說“七十稀”、“廿一枝”和“正半月”，就是暗指這三個關(guān)鍵的數(shù)字?！秾O子算經(jīng)》沒有說明這三個數(shù)的來歷。實際上，它們具有如下特性：也就是說，這三個數(shù)可以從最小公倍數(shù)M

4、=3×5×7=105中各約去模數(shù)3、5、7后，再分別乘以整數(shù)2、1、1而得到。假令k1=2，K2=1，K3=1，那么整數(shù)Ki（i=1，2，3)的選取使所得到的三數(shù)70、21、15被相應(yīng)模數(shù)相除的時候余數(shù)都是1。由此出發(fā)，立即可以推出，在余數(shù)是R1、R2、R3的情況下的情況。Word文檔解法中的三個關(guān)鍵數(shù)70，21，15，有何妙用，有何性質(zhì)呢?首先70是3除余1而5與7都除得盡的數(shù)，所以70a是3除余a，而5與7都除得盡的數(shù)，21是5除余1，而3與7都除得盡的數(shù)，所以21b是5除余b，而3與7除得盡的數(shù)。同理，15c

5、是7除余c，3與5除得盡的數(shù)，總加起來70a+21b+15c是3除余a，5除余b，7除余c的數(shù)，也就是可能答案之一，但可能不是最小的，這數(shù)加減105(105=3×5×7)仍有這樣性質(zhì)，可以多次減去105而得到最小的正數(shù)解。附：如70，其實是要找余2的，但只要找到了余1的再乘2即余二了。孫子問題的解法，以現(xiàn)代的說法，是找出三個關(guān)鍵數(shù)70，21，15。解法的意思就是用70乘3除所得的余數(shù)，21乘5除所得的余數(shù)，15乘7除所得的余數(shù)，然后總加起來，除以105的余數(shù)就是答案。即題目的答案為70×2+21×3+15×2=14

6、0+63+30=233233-2×105=23公式：70a+21b+15c-105n題中有三個數(shù)，分別為3、5、7，5×7÷3余數(shù)為2，取35；3×7÷5余數(shù)為1，要使余數(shù)為3，只需將3×7擴大3倍變成63即可；同樣3×5÷7的余數(shù)為1，要使余數(shù)為2，則將3×5擴大2倍，變成30。中國剩余定理”算理及其應(yīng)用：為什么這樣解呢？因為70是5和7的公倍數(shù)，且除以3余1。21是3和7的公倍數(shù)，且除以5余1。15是3和5的公倍數(shù)，且除以7余1。（任何一個一次同余式組，只要根據(jù)這個規(guī)律求出那幾個關(guān)鍵數(shù)字，那么這個一次同余式組就

7、不難解出了。）把70、21、15這三個數(shù)分別乘以它們的余數(shù)，再把三個積加起來是233，符合題意，但不是最小，而105又是3、5、7的最小公倍數(shù)，去掉105的倍數(shù)，剩下的差就是最小的一個答案。用歌訣解題容易記憶，但有它的局限性，只能限于用3、5、7三個數(shù)去除，用其它的數(shù)去除就不行了。后來中國數(shù)學(xué)家又研究了這個問題，運用了像上面分析的方法那樣進行解答。例1：一個數(shù)被3除余1，被4除余2，被5除余4，這個數(shù)最小是幾？題中3、4、5三個數(shù)兩兩互質(zhì)。則〔4，5〕=20；〔3，5〕=15；〔3，4〕=12；〔3，4，5〕=60

8、。為了使20被3除余1，用20×2=40；使15被4除余1，用15×3=45；使12被5除余1，用12×3=36。然后，40×1+45×2+36×4=274，因為，274>60，所以，274－60×4=34，就是所求的數(shù)。Word文檔例2：一個數(shù)被3除余2，被7除余4，被8除余5，這個數(shù)最小是幾？題中3、7、8三個數(shù)兩兩互質(zhì)。則〔7，8〕=56；〔3，8〕=