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

淺析中國剩余定理及其應(yīng)用李輝（井岡山學(xué)院數(shù)理學(xué)院信息與計算科學(xué)343009）指導(dǎo)老師顏昌元[摘要]：本文闡述了中國剩余定理的由來，介紹了它的幾種解法，及其它在多項式，現(xiàn)代密碼學(xué)，生活方面的應(yīng)用.[關(guān)鍵詞]：中國剩余定理；解法;多項式；現(xiàn)代密碼學(xué)引言在中國,以剩余定理為代表的同余理論源遠(yuǎn)流長,可追溯到《周易》中的卜筮古法.秦九韶說:“圣有大衍,微寓于《易》”,即指此意.另外,同余理論的另一個來源是古代制定歷法的需要.實際上,從漢末到宋末1000余年的時間中,有很多天文學(xué)家熟悉一次同余式的解法,他們在編制歷法時利用它來推算“上元積年”.中國剩余定理對現(xiàn)代數(shù)學(xué)的研究有很強的啟迪意義.特別是在多項式，密碼學(xué)中的應(yīng)用非常關(guān)鍵.一中國剩余定理的由來我國古代《孫子算經(jīng)》中有一著名而又重要的問題:“今有物不知其數(shù),三三數(shù)之剩二、五五數(shù)之剩三,七七數(shù)之剩二,問物幾何.答曰:二十三”.這一問題可譯為:一個數(shù)除以3余2,除以5余3,除以7余2.求適合條件的最小的數(shù).題中還介紹了它的解法:“術(shù)曰:三三數(shù)之剩二,置一百四十;五五數(shù)之剩三,置六十三;七七數(shù)之剩二,置三十;并之,得二百三十三,以二百十減之,即得.”意即:物數(shù)W=70×2+21×3+15×2-2×105=23.接下來又給出了這類題的一般解法(余數(shù)為一的情況):術(shù)文說:“凡三三數(shù)之剩一,則置七十;五五數(shù)之剩一,則置二十一;七七數(shù)之剩一,則置十五.一百六以上,以一百五減之,即得.”這個問題及其解法,在世界數(shù)學(xué)史上占有重要的地位,因此,中外數(shù)學(xué)家都尊稱為“孫子定理”或“中國剩余定理”.為了比較清楚地了解“中國剩余定理”這一名稱的由來,我們不妨先引進同余定義:一般地,若兩個整數(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)的解是:N=70a+21b+15c-105P(1)現(xiàn)在,我們把上述解法中的a,b,c作一分析:設(shè)M=3×5×7,則70=2×5×7=2×(3×5×7)/3=2×M/321=3×7=1×(3×5×7)/5=1×M/515=3×7=1×(3×5×7)/7=1×M/7因此,問題的解(1)式可以寫成:N=2×M/3a+1×M/5b+1×M/7c當(dāng)時歐洲的數(shù)學(xué)家們對中國古代數(shù)學(xué)毫無所知.德國數(shù)學(xué)家高斯(1777~1855)通過獨立研究,于公元1801年出版的《算術(shù)探究》上發(fā)表了著名的高斯定理:設(shè)為兩兩互質(zhì)的h個除數(shù),各為余數(shù),,,,如果我們找得到滿足,那么.我們把孫子的“物不知其數(shù)”問題的解法與高斯定理一對照,不難看出:高斯定理實質(zhì)上就是孫子解法的推廣.公元1852年,英國基督教士偉烈亞力將《孫子算經(jīng)》中的“物不知其數(shù)”問題的解法傳到歐洲。公元1874年,馬蒂生指出:孫子的解法完全符合高斯的定理。而此時,高斯定理已比《孫子算經(jīng)》中的“物不知其數(shù)”問題的解法晚一千五百多年.從此,在西文的數(shù)學(xué)史上將“物不知其數(shù)”問題稱為“中國剩余定理”或“孫子定理”.二中國剩余定理的解法中國剩余定理的解法有許多，本文就介紹幾種常見的，歌訣法，不定方程解法，同余解法。其余的解法就不一一介紹，每種解法有它的優(yōu)點，最基礎(chǔ)的還是歌訣法.2.1歌訣法2.1.1兩個算數(shù)定理定理1被除數(shù)增加(或減少)除數(shù)的倍數(shù),除數(shù)不變,則余數(shù)也不變.即:如果a÷b=q(余r),則(a+bn)÷b=q+n(余r)(n∈Z).證明∵a÷b=q(余r)則a=bq+r∴a+bn=(q+n)b+r,即(a+bn),b=q+n(余r)定理2被除數(shù)擴大(或縮小)幾倍,除數(shù)不變,則余數(shù)也擴大(或縮小)同數(shù)倍.即:如果a÷b=q(余r),那么an÷b=qn(余rn);若rn>b,則余rn-bm使rn-bm<b(m,n∈Z),則:an÷b=qn+m(余rn-bm)證明由a÷b=q(余r)a=bq+r,則an=b(nq)+rn,所以an÷b=nq(余rn)2.1.2解法歌訣明朝程大位編著的《算法統(tǒng)宗》(公元1592年)里記載了此題的解法,他是用一首歌謠(孫子歌)敘述出來的:“三人同行七十稀,五樹梅花廿一枝,七子團圓正月半,除百零五便得知.”它的每句歌謠都隱藏著解題需要的數(shù).“三(3)人同行七十(70)稀”,即用被3除所得的余數(shù)乘以70.“五(5)樹梅花廿一(21)枝”,即用被5除所得的余數(shù)乘以21.“七(7)子團圓正月半(15)”,即用被7除所得的余數(shù)乘以15.“除百零五(105)便得知”,是說把上面所得的三個積相加,如果和大于105,就減去105的若干倍,直到差小于105為止,得出的差就是所求的最小正整數(shù).解答算式是:70×2+21×3+15×2=233,233-105×2=232.1.3解法的理由及步驟①先在5與7的公倍數(shù)中找除以3余1的數(shù),進而找到除以3余2的數(shù).∵[5,7]=3535÷3=11(余2),由定理2(35×2)÷3=23(余1)而(70×2)÷3=46(余2),所以140是符合條件的數(shù).②在3與7的公倍數(shù)中找除以5余3的數(shù).∵[3,7]=2121÷5=4(余1)由定理221×3÷5=12(余3)即63符合條件③在3與5的公倍數(shù)中找除以7余2的數(shù).∵[3,5]=1515÷7=2(余1)由定理215×2÷7=4(余2)即30符合條件④將上面得到的分別符合三個條件的三個數(shù)相加:70×2+21×3+15×2=233∵140加上的數(shù)都是3的倍數(shù),∴除以3的余數(shù)不變(定理1);即233滿足除以3余2的條件,同理可知,233也滿足題目中的另外兩個條件,即物數(shù)W=233就是本題的一個解,又∵[3,5,7]=105,再由定理1可知,233-2×105=23也是它的解,又∵23<105,∴Wmin=23.上面的解法中,總是先求出余1的數(shù),再求出余幾的數(shù),這種解法逐漸被總結(jié)為簡潔實用的“求一術(shù)”.其實,早在宋朝的周密就曾把這個題目的解法編成如下的歌謠“三歲孩兒七十稀,五留廿一事尤奇,七度上元重相會,寒食清明便可知”.這里的“上元”指十五,而“寒食”指清明的前一天,冬至后106天是清明節(jié),所以冬至到寒食為105天.歌謠中將解題所用各數(shù)暗暗給出,增加了題目的趣味性和神秘性.2.2.4不定方程解法設(shè)物數(shù)為W,W被3、5、7除所得的不完全商分別為x、y、z則有:消去W,得到3x-5y=1(4)3x=7z(5)由(5)式得x=7z/3令(∈N),得(6)從而有y=(21-1)/5=4+(-1)/5,再令(-1)/5=(∈N)則=5+1∴x=35+7y=+4z=15+3,W=105+23,這就是“物不知數(shù)”問題的通解公式,顯然當(dāng)=0時,有最小正整數(shù)解W=23.1.3同余解法“物不知數(shù)”問題用同余式組來表達(dá),即解由(1)得W=(4)代入(2)式得≡3(mod5)3≡1(mod5)3≡6(mod5)≡2(mod5)=2+5,將其代入(4)式有W=8+15(5)由(5),(3)兩式,8+15=2(mod7)8+15≡9(mod7)15≡1(mod7)15≡15(mod7)≡1(mod7)=1+7,將代入(5)式,得W=23+105,即W=23(mod105)∵3、5、7兩兩互質(zhì),所以W≡23(mod105)是同余式組的解.在《孫子算經(jīng)》中給出的解答實質(zhì)上就是W≡70×2+21×3+15×2≡140+63+30≡233≡23(mod105)三中國剩余定理的應(yīng)用中國剩余定理是我國古代數(shù)學(xué)家為世界數(shù)學(xué)發(fā)展作出的巨大貢獻,它的數(shù)學(xué)思想在近代數(shù)學(xué)、當(dāng)代密碼學(xué)研究及日常生活都有著廣泛應(yīng)用.中國剩余定理：設(shè)是兩兩互素的正整數(shù)，設(shè)是整數(shù)，則同余方程組，模有惟一解,其中,.3.1中國剩余定理在多項式中的應(yīng)用由中國剩余定理可得相似定理,設(shè)是n個兩兩互素的多項式,是n個多項式,則一定存在多項式,使當(dāng)f(s)的次數(shù)不超過的次數(shù)時,f(x)唯一確定.特別地,當(dāng)（或），i=1,2,…,n是互不相等的常數(shù),從而（i=1,2,…,n）也就是兩兩互素的多項式,由余數(shù)定,(i=1,2,…,n)從而定理可敘述為,一定存在多項式f(x),使其中(i=1,2,…,n)是任意給定的常數(shù),且多項式f(x)在次數(shù)不超過n的條件下是唯一確定的,由f(x)≡等價于(i=1,2,…,n)得:對任意的互不相同的(i=1,2,…,n)及任意的(i=1,2,…,n)存在唯一的次數(shù)小于n的多項式f(x),使(i=1,2,…,n).這就是插值多項式的存在與唯一性定理.由中國剩余定理的證法,只要找到多項式(i=1,2,…,n),使而滿足上式,于是得插值多項式f(x):這就是著名的Lagrange內(nèi)插多項式.中國剩余定理推導(dǎo)出的內(nèi)插多項式是處理許多多項式問題的基本工具,如簡化數(shù)列求和問題:3.1.1計算解假設(shè)和為n的三次多項式f(n),n代表項數(shù),于是有f(0)=0,f(1)=0,f(2)=1,f(3)=5由插值公式得所以,=3.1.2設(shè)f(x)以的余式分別為4x+4,4x+8,求f(x)除以的余式.解由條件可得f(x)≡4x+4(mod)f(x)≡4x+8(mod)注意到與互素,且(-1)·+1·=1,由上面及其證明可得f(x)≡(4x+4)·1·()+(4x+8)·(-1)·()(mod()(),因此f(x)除以()()的余式為(4x+4)()-(4x+8)()=4x-43.1.3設(shè)f(x)被x-1,x-2,x-3除后,所得的余式分別4,8,16,求f(x)被(x-1)(x-2)(x-3)除后的余式.解設(shè)f(x)=p(x)(x-1)(x-2)·(x-3)+r(x),其中r(x)的次數(shù)小于3,從條件可得由Lagrange插值公式直接得到：=中國剩余定理主要是解決一次同余式問題,在算術(shù)中還可以利用它來檢查因數(shù)和驗算整數(shù)計算的結(jié)果.2中國剩余定理在現(xiàn)代密碼學(xué)中的應(yīng)用公開密鑰密碼算法又稱為非對稱密碼算法,在計算機網(wǎng)絡(luò)和電子商務(wù)中的應(yīng)用日趨成熟.RonRivest和AdiShamir以及LeonardAdleman于1978年提出的RSA公鑰密碼體制至今仍被認(rèn)為是一個安全性能良好的密碼體制.RSA公鑰密碼體制描述如下：選取兩個大素數(shù)p和q（保密).計算n=pq（公開），Φ(n)=(p-1)(q-1)（保密）.隨機選取正整數(shù)e,1<e<Φ(n),滿足gcd(e,Φ(n))=1,e是公開的加密密鑰.計算d，滿足.d是保密的解密密鑰.加密變換：對明文，密文為：.解密變換：對密文，明文為：3中國剩余定理在生活中的應(yīng)用在日常生活中我們所要注意的往往不是某些整數(shù),而是這些數(shù)用某一固定的數(shù)去除所得的余數(shù).例如:假定現(xiàn)在是早上9點,在兩個小時前是幾點呢?我們會立刻得到正確的答案是早上7點;那么過了十三個小時后,又是幾點呢?算式為9+13-12=10即晚上10點;在28小時之后,手表指針又會指到幾點呢?算式為(9+28)-(3×12)=1即1點.解此問題的方法是:若現(xiàn)在時間是A,問經(jīng)過B小時之后的時間.只需算A+B=C(mod12),余數(shù)C就是手表的小時數(shù).四總結(jié)中國剩余定理堪稱數(shù)學(xué)史上名垂百世的成就,它在數(shù)學(xué)史上占有光輝的一頁,其數(shù)學(xué)思想一直啟發(fā)和指引著歷代數(shù)學(xué)家們,在數(shù)學(xué)領(lǐng)域,特別是計算機領(lǐng)域發(fā)揮著重要作用.以上只是它應(yīng)用的一些例子。同時，在密碼學(xué)領(lǐng)域，它的作用一樣非常重要，現(xiàn)代密碼的解密和保密算法都需要中國剩余定理?？梢娭袊Ｓ喽ɡ淼膽?yīng)用之廣泛,地位之高.我國獲得“第一屆國家最高科學(xué)技術(shù)獎”的當(dāng)代大數(shù)學(xué)家吳文俊,在深入研究中國古代數(shù)學(xué)的基礎(chǔ)上,總結(jié)出中國傳統(tǒng)數(shù)學(xué)具有兩大特色:機械化和構(gòu)造性,在此啟發(fā)下從事幾何定理機器證明的研究,取得了創(chuàng)造性的成就,成為近代數(shù)學(xué)史上開創(chuàng)新領(lǐng)域的第一人,由此可見,中國傳統(tǒng)數(shù)學(xué)博大精深,是我們?nèi)≈唤叩膶氋F財富,繼承中國的數(shù)學(xué)遺產(chǎn)的遠(yuǎn)景相當(dāng)廣闊,有待我們的不斷努力.參考文獻[1]陳景潤.初等數(shù)論[M]北京:科學(xué)出版社,1978.[2]謝邦杰.抽象代數(shù)學(xué)[M].上海:上?？茖W(xué)技術(shù)出版社,1982.[3]戴執(zhí)中賦值論概要[M].北京:人民教育出版社,1982.[4]李文林.數(shù)學(xué)史教程[M].北京:高等教育出版社,2004.[5]陳魯生等現(xiàn)代密碼學(xué)[M]北京科學(xué)出版社，2