淺析中國剩余定理及其應(yīng)用

1、淺析中國剩余定理及其應(yīng)用淺析中國剩余定理及其應(yīng)用李輝（井岡山學(xué)院數(shù)理學(xué)院信息與計算科學(xué)343009）指導(dǎo)老師顏昌元[摘要摘要]：本文闡述了中國剩余定理的由來，介紹了它的幾種解法，及其它在多項式，現(xiàn)代密碼學(xué)，生活方面的應(yīng)用.[關(guān)鍵詞關(guān)鍵詞]：中國剩余定理；解法多項式；現(xiàn)代密碼學(xué)引言引言在中國以剩余定理為代表的同余理論源遠(yuǎn)流長可追溯到《周易》中的卜筮古法.秦九韶說:“圣有大衍微寓于《易》”即指此意.另外同余理論的另一個來源是古代制定歷法的需

2、要.實際上從漢末到宋末1000余年的時間中有很多天文學(xué)家熟悉一次同余式的解法他們在編制歷法時利用它來推算“上元積年”.中國剩余定理對現(xiàn)代數(shù)學(xué)的研究有很強(qiáng)的啟迪意義.特別是在多項式，密碼學(xué)中的應(yīng)用非常關(guān)鍵.一中國剩余定理的由來中國剩余定理的由來我國古代《孫子算經(jīng)》中有一著名而又重要的問題:“今有物不知其數(shù)三三數(shù)之剩二、五五數(shù)之剩三七七數(shù)之剩二問物幾何.答曰:二十三”.這一問題可譯為:一個數(shù)除以3余2除以5余3除以7余2.求適合條件的最小的

3、數(shù).題中還介紹了它的解法:“術(shù)曰:三三數(shù)之剩二置一百四十五五數(shù)之剩三置六十三七七數(shù)之剩二置三十并之得二百三十三以二百十減之即得.”意即:物數(shù)W=7022131522105=23.接下來又給出了這類題的一般解法(余數(shù)為一的情況):術(shù)文說:“凡三三數(shù)之剩一則置七十五五數(shù)之剩一則置二十一七七數(shù)之剩一則置十五.一百六以上以一百五減之即得.”這個問題及其解法在世界數(shù)學(xué)史上占有重要的地位因此中外數(shù)學(xué)家都尊稱為“孫子定理”或“中國剩余定理”.為了比較

4、清楚地了解“中國剩余定理”這一名稱的由來我們不妨先引進(jìn)同余定義:一般地若兩個整數(shù)a、b被同一個大于1的整數(shù)m除有相同的余數(shù)那么稱a、b對于模m同余.記作:a≡b(modm）應(yīng)用同余原理我們把“物不知其數(shù)”問題用整數(shù)的同余式符號表達(dá)出來是:設(shè)N≡2(mod3)≡3(mod5)≡2(mod7)求最小的數(shù)N.答案是N=23.書中問題及其解法建立起數(shù)學(xué)模型就是:設(shè)a、b、c為余數(shù)P為整數(shù)則N≡a(mod3)≡b(mod5)≡c(mod7)的解是

5、:N=70a21b15c105P(1)現(xiàn)在我們把上述解法中的abc作一分析:設(shè)M=357則70=257=2(357)3=2M3“七(7)子團(tuán)圓正月半(15)”即用被7除所得的余數(shù)乘以15.“除百零五(105)便得知”是說把上面所得的三個積相加如果和大于105就減去105的若干倍直到差小于105為止得出的差就是所求的最小正整數(shù).解答算式是:702213152=2332331052=232.1.3解法的理由及步驟①先在5與7的公倍數(shù)中找除以

6、3余1的數(shù)進(jìn)而找到除以3余2的數(shù).∵[57]=35353=11(余2)由定理2(352)3=23(余1)而(702)3=46(余2)所以140是符合條件的數(shù).②在3與7的公倍數(shù)中找除以5余3的數(shù).∵[37]=21215=4(余1)由定理22135=12(余3)即63符合條件③在3與5的公倍數(shù)中找除以7余2的數(shù).∵[35]=15157=2(余1)由定理21527=4(余2)即30符合條件④將上面得到的分別符合三個條件的三個數(shù)相加:7022

7、13152=233∵140加上的數(shù)都是3的倍數(shù)∴除以3的余數(shù)不變(定理1)即233滿足除以3余2的條件同理可知233也滿足題目中的另外兩個條件即物數(shù)W=233就是本題的一個解又∵[357]=105再由定理1可知2332105=23也是它的解又∵23105∴Wmin=23.上面的解法中總是先求出余1的數(shù)再求出余幾的數(shù)這種解法逐漸被總結(jié)為簡潔實用的“求一術(shù)”.其實早在宋朝的周密就曾把這個題目的解法編成如下的歌謠“三歲孩兒七十稀五留廿一事尤奇

8、七度上元重相會寒食清明便可知”.這里的“上元”指十五而“寒食”指清明的前一天冬至后106天是清明節(jié)所以冬至到寒食為105天.歌謠中將解題所用各數(shù)暗暗給出增加了題目的趣味性和神秘性.2.2.4不定方程解法設(shè)物數(shù)為WW被3、5、7除所得的不完全商分別為x、y、z則有:W=3x2(1)W=5y3(2)(WxyzN)W=7z2(3)??????消去W得到3x5y=1(4)3x=7z(5)由(5)式得x=7z3令(∈N)得13zt?1t13zt?