中國剩余定理的應(yīng)用
2010-12-31 00:00:00張麗清
科教導(dǎo)刊 2010年15期
摘要中國剩余定理又稱為孫子定理，它的數(shù)學(xué)思想在近代數(shù)學(xué)中占有非常重要的地位。本文歸納并綜述了中國剩余定理及其在數(shù)論、多項式理論、賦值理論及密碼學(xué)等方面的具體應(yīng)用。
關(guān)鍵詞中國剩余定理 多項式理論 賦值理論
中圖分類號:O119文獻標(biāo)識碼:A
0引言
我國古算書《孫子算經(jīng)》(中國古代數(shù)學(xué)著作，成書于公元5—6世紀(jì)(?))下卷中，有個非常著名的數(shù)學(xué)問題，“物不知其數(shù)問題”:今有物不知其數(shù)，三三數(shù)之剩二，五五數(shù)之剩三，七七數(shù)之剩二，問物幾何?答曰:23。
用現(xiàn)代數(shù)學(xué)語言表述，就是求整數(shù)n，使得:
這是一次同余方程組問題，《孫子算經(jīng)》除給出了這道題的解法和答案外，還給出了這一類問題的解法“術(shù)文”:凡三三數(shù)之剩一則置七十，五五數(shù)之剩一則置二十一，七七數(shù)之剩一則置十五，一百六以上以一百五減之，即得。此文中的“一百六”，“一百五”，古指“106”和“105”。
《孫子算經(jīng)》的“物不知其數(shù)”題雖然開創(chuàng)了一次同余式研究的先河，但真正從完整的計算程序和理論上解決這個問題的是南宋數(shù)學(xué)家秦九韶，他在他的《數(shù)學(xué)九章》中提出了一個數(shù)學(xué)方法，稱之為“大衍求一術(shù)”。
1876年，德國人馬蒂生首先提出這一解法與19世紀(jì)高斯的《算術(shù)探究》中關(guān)于一次同余式組的解法完全一致。從此，中國古代數(shù)學(xué)的這一創(chuàng)造逐漸受到世界學(xué)者的矚目，并在西方數(shù)學(xué)史著作中正式被稱為“中國剩余定理”。
1中國剩余定理
將《孫子算經(jīng)》中所用的求解“物不知其數(shù)”問題的方法加以推廣，就成為:
定理1 (中國剩余定理)設(shè)m1，m2，…，mk是k 個兩兩互素的正整數(shù)，，m = m1，m2，…，mk，m = miMi(i=1，2， …，k)，則同余式組
有唯一解x = M1'M1b1+M2'M2b2+…+Mk'Mkbk(modm)
其中，Mi'Mi= 1(modmi)(i = 1，2，…，k).
學(xué)者們將中國剩余定理推廣到其他數(shù)學(xué)領(lǐng)域中，得到中國剩余定理以下幾種不同的表述:
定理2(環(huán)的中國剩余定理)設(shè)R是環(huán)，J1，J2，…，Jn是R的理想，滿足Ji + Jj = R，1≤i，j≤n，i≠j，(稱為J1，J2，…，Jn間兩兩互素)，則有環(huán)同構(gòu):
定理3(環(huán)的中國剩余定理)設(shè)R是有單位元1(≠0)，的環(huán)，它的理想I1，I2，…，IS兩兩互素，則對于任意給定的s個元素b1，b2，…，bS∈R，同余方程式
在R內(nèi)必有解;并且如果a，c是兩個解，則
定理4(模的中國剩余定理)設(shè)R是一個交換環(huán)，R未必有單位元，M是一個R—模，N1，N2，…，Nn是M的n 個子模，則對任意的x1，x2，…，xn∈M，存在x∈M，使得x≡xi(modNi)(i=1，2，…n)，當(dāng)且僅當(dāng).
2 中國剩余定理的應(yīng)用
中國剩余定理是我國古代數(shù)學(xué)家為世界數(shù)學(xué)發(fā)展作出的巨大貢獻，是數(shù)論中一個很重要的定理，它的數(shù)學(xué)思想在近代數(shù)學(xué)，密碼學(xué)研究中都有著廣泛的應(yīng)用。
2.1 中國剩余定理在數(shù)論中的應(yīng)用
(1)中國剩余定理在數(shù)論中的占有很重要的地位，應(yīng)用十分廣泛。直接應(yīng)用公式求解未知系數(shù)為1，模兩兩互素的一次同余方程組，關(guān)鍵是求乘率，也就是要解同余式，這個同余式的一般解法也就是秦邵所說的“求一術(shù)”。
例1:韓信點兵:有兵一隊，若列成五行縱隊，則末行一人，成六行縱隊，則末行五人，成七行縱隊，則末行四人，成十一行縱隊，則末行十人，求兵數(shù)。
解:依題意可得同余方程組:
同理依次解得M2'=1，M3'=1，M4'=1。由中國剩余定理得
x≡3€?62€?+1€?85€?+1€?30€?+1€?10€?0≡6731≡2111(mod2310)
(2)對于一般一次同余式組，即模為任意正整數(shù)，系數(shù)為任意整數(shù)的一次同余式組，雖然不能直接用中國剩余定理求解，但可以通過等價處理同余式組后，再利用中國剩余定理求解。為了便于說明，先介紹兩個定理:
定理5設(shè)m1，m2，…，mk是k個整數(shù)，則同余式組
有解的充要條件是(mi，mj)|xi-xj，i，j=1，2，…，k。并且若有兩解，對模m=[m1，m2，…，mk]有唯一解。
定理6 設(shè)m1，m2，…，mn為正整數(shù)，其標(biāo)準(zhǔn)分解式分別為:
，
當(dāng)同余式組
有解，則其解與同余式組
的解完全相同。
有這兩個定理后，一般的一次同余式也都能解了。
例2:解同余方程組
解:由于(8，20) = 4，11≡3(mod4) ;(8，5) = 1，3≡1(mod1) ; (20，5) = 5，11≡1(mod5)所以原同余方程組有解且存在唯解。
(20，5) = 5，11≡1(mod5)，m2 = 20=22€?，m3=15=3€?。
由定理6，原同余方程組同解于: (3-1)
由中國剩余定理得(3-1)的解為:
x = 7€?5€?+4€?4€?+1€?0€?≡451≡91(mod120)
(3)利用中國剩余定理還可以證明高次同余式有解的問題。
定理:若m1，m2，…，mk是k 個兩兩互素的正整數(shù)，m = m1m2… mk，則同余式f(x)≡0(modm)
有解的充分必要條件是同余式f(x)≡0(modmi)(i = 1，2，…，k)的每一個有解。并且，若用Ti表示
f(x)≡0(modmi)(i =1，2，…，k)的解數(shù)，T表示f(x)≡0(modm)的解數(shù)，則T = T1T2…Tk。
證明:(1)設(shè)x0是f(x)≡0(modm)的解，即f(x0)≡0(modm)，得f(x0)≡0(modmi)(i = 1，2，…，k)
即x0是f(x)≡0(modmi)(i = 1，2，…，k)的解。
假設(shè)xi是f(x)≡0(modmi)(i = 1，2，…，k)的解，即f(xi)≡0(modmi)(i = 1，2，…，k)，因為1≤i≤j≤k時，(mi，mj) = 1，由中國剩余定理，有惟一的x0，0≤x0 < m，滿足x0≡xi(modmi)(i = 1，2，…，k)，且f(x0)≡f(xi)≡0(modmi)(i = 1，2，…，k)，故f(x0)≡0(modm) ，這就證明了同余式f(x)≡0(modm)有解的充要條件是同余式組f(x)≡0(modmi)(i =1，2，…，k)的每一個有解。
(2)設(shè)f(x)≡0(modmi)的Ti個不同的解是x0≡ui，ei(modmi)，0≤ui，ei < m，(ei = 1，2，…，Ti，i=1，2，…，k).對其中任一組(u1，ei ，…，uk，ek) ，由中國剩余定理可得惟一的x，0≤x 反之，設(shè)x1，…，xT，0≤xi < m(i=1，2，…，T)，是f(x)≡0(modm)的T個解，則對某個j(1≤j≤T)，( 綜上所述，就證明了T = T1T2…Tk。 結(jié)合上述定理，就可以利用中國剩余定理求解高次同余式。 (4)中國剩余定理反映了滿足條件的同余方程組一定有解，這就為一些關(guān)于數(shù)論中的存在性問題的解決提供了有利的工具。下面這道例題就是通過構(gòu)造同余方程組，利用中國剩余定理解決問題的。 例3:是否存在21個相繼正整數(shù)，其中每個數(shù)至少可被一個不小于2，不大于13的素數(shù)整除?(第15屆美國數(shù)學(xué)奧林匹克) 解:設(shè)這21個相繼正整數(shù)為N-10，N-9，N-8，…，N-1，N，N+1，…，N+10，如果N=2€?€?€?k，那么N-10，…，N-2，N，N+2，…，N+10中的每一個都至少被2，3，5，7中的一個整除。下面設(shè)法使N-1能被11整除，N+1能被13整除，這樣本題就可得證。 由于2€?€?€?，11，13，這三個數(shù)兩兩互素，由中國剩余定理知，同余方程組 (3-2) 有解。設(shè)這個解為N，則N-1，N+1，分別能被11和13整除。 于是，由此得到的21個相繼正整數(shù)即為所求。由方程組(3-2)解得x = 9450(mod30030)，即x = 9450+30030t，當(dāng)t = 0時，得到的21個相繼正整數(shù)是:9440，…， 9450，…，9460. 例4:是否存在1000000個相繼的整數(shù)，使得每個都含有重復(fù)的素因子，即都被某個素數(shù)的平方整除。(第15屆普特南數(shù)學(xué)競賽) 這道題可以用數(shù)學(xué)歸納法證明，但是證明過程繁瑣。其實這個題目的1000000并不是關(guān)鍵，用中國剩余定理可以證明更強的命題:存在n個相繼正整數(shù)，使得每一個都含有重復(fù)的素因子。 事實上，如果存在n個相繼的正整數(shù)m+1，m+2，…，m+n，那么，這題的目標(biāo)就是證x≡-i(modpi2)有解，而這就是中國剩余定理。 證明:令p1，p2，…，pn是n個相異的素數(shù)，由中國剩余定理，同余方程組 有解。設(shè)這個解為 m，則n個相繼的整數(shù)m+1，m+2，…，m+n中的每一個都能被某個素數(shù)的平方整除。 從以上證明過程可以看出，中國剩余定理在證明存在性問題的作用。 2.2 中國剩余定理在多項式理論中的應(yīng)用 在多項式理論中，我們知道有這樣一個定理:若f(x)與g(x)是兩兩互素的多項式，則一定存在另兩個多項式h(x)與k(x)，使h(x)f(x)+k(x)g(x) = 1。證明中國剩余定理正是運用了這一性質(zhì)，類似的也可得與中國剩余定理相似的一個定理: 設(shè)m1(x)，m2(x)，…，mn(x)是n個兩兩互素的多項式，a1(x)，a2(x)，…，an(x)是n個任給的多項式，則一定存在多項式f(x)滿足: 并且在modm(x)(m(x) = m1(x)m2(x)…mn(x))下是惟一的，當(dāng)f(x)的次數(shù)不超過m(x)的次數(shù)時，f(x)惟一確定。 特別地，當(dāng)mi(x) = x-b∈Q[x](或R[x])，i = 1，2，…，n，bi(i = 1，2，…，n)是互不相等的常數(shù)，從而mi(x)(i = 1，2，…，n)也就是兩兩互素的多項式，由余數(shù)定理可知，mi(x)≡mi(bi)(mod(x-bi))，(i =1，2，…，n)，從而定理可敘述為，一定存在多項式f(x)，使 其中ai(x)(i = 1，2，…，n)是任意給定的常數(shù)，且多項式f(x)在次數(shù)不超過n的條件下是惟一確定的，由f(x)≡ai(x)mod(x-bi)等價于f(bi) ≡ ai(i = 1，2，…，n)得:對任意的互不相同的bi(i =1，2，…，n)及任意的ai(i =1，2，…，n)，存在惟一的次數(shù)小于n的多項式f(x)，使f(bi) = ai (i=1，2，…，n)，這就是插值多項式的存在與惟一性定理。 由中國剩余定理的證法，只要找到多項式Mi(x)(i=1，2，…，n)，使 (3-3) 而 滿足(3-3)，于是得插值多項式: 這就是著名的Lagrange內(nèi)插多項式。 中國剩余定理推導(dǎo)出的內(nèi)插多項式是處理許多多項式問題的基本工具，如簡化數(shù)列求和問題:計算02+12+22+…+(n-1)2 解:假設(shè)和為n的三次多項式f(n)，n代表項數(shù)，于是有 f(0) = 0，f(1) = 0，f(2) =1，f(3) = 5 由插值公式得 所以，02+12+22+…+(n-1)2= n(n-1)(2n-1) 2.3 中國剩余定理在賦值理論中的應(yīng)用 賦值理論是域論的一個分支，是研究近代數(shù)學(xué)中幾個重要分支，如代數(shù)數(shù)論、交換數(shù)論的一個重要工具，而中國剩余定理在賦值理論中起著重要作用。先敘述一些預(yù)備知識。 定義:設(shè)p∈Z，且p為素數(shù)，a∈Q，且a≠0，令a = pl，其中，p/m，p/n，l，m，n∈Z，則a的p賦值為vp(a) = p-l.又令vp(0)=0，兩個有理數(shù)a，b的p距離為Dp(a，b) = vp(a-b)。 P賦值vp有 如下的性質(zhì): P距離Dp有如下性質(zhì): 定理(賦值的獨立性)對任意的n個p賦值Vp1，Vp2，…，Vpna∈Q，i=1，2，…，n，以及任意>0，p-l1，p-l2，…，p-ln則存在b∈Q，使 (下轉(zhuǎn)第96頁) (上接第50頁) 證明:設(shè)m為a1，a2，…，an的最小公分母， 令 r =max{1，r1，r2，…，rn}，根據(jù)中國剩余定理，可求得一個c，使得 即 . 設(shè)q = (p1p2…pn)r，取適當(dāng)?shù)膗，v∈z，使|-a|<， 再令 = b，則b顯然滿足條件(1)，又由p距離Dp的性質(zhì):，有 3 結(jié)束語 中國剩余定理在數(shù)學(xué)史上占有光輝的一頁，它在數(shù)論及近代數(shù)學(xué)領(lǐng)域是非常重要的理論，起著基礎(chǔ)作用，并有著廣泛的應(yīng)用。以上所歸納的只是它應(yīng)用的一些例子，中國剩余定理的思想方法及對此定理的直接應(yīng)用還體現(xiàn)在近代數(shù)學(xué)的很多地方。 參考文獻 [1]柯召，孫琦.數(shù)論講義[M].北京:高等教育出版社，2003:42-44. [2]丘維聲 .抽象代數(shù)基礎(chǔ)[M].北京:高等教育出版社，2003:129-133. [3]石生明.近世代數(shù)初步[M].北京:高等教育出版社，2002:133-136. [4]閔嗣鶴，嚴(yán)士健.初等數(shù)論[M].北京:高等教育出版社，2006:76-78. [5]張紹康.中國剩余定理思想在近代數(shù)學(xué)中的體現(xiàn)[J].昭通師專學(xué)報，1998.20 (3-4):124-126. [6]王連笑.孫子定理與數(shù)論中的存在問題 [J].中等數(shù)學(xué)，1994.4:7-8. [7]王海鵑，王鎂銜.中國剩余定理及其應(yīng)用[J].通化師范學(xué)院學(xué)報，2005.26(6):12-13. [8]唐高華.關(guān)于模的中國剩余定理[J].廣西師院學(xué)報(自然科學(xué)報)，1995.1:30-32. [9]陳鋼.孫子定理[J].湖南教育，1995.4 :45. [10]宴能中.孫子定理的推廣和應(yīng)用[J].達縣師專學(xué)報(自然科學(xué)版)，1994.4: 50-51. [11]劉曉衛(wèi)，王書琴.剩余定理及一次同余式組[J].哈爾濱師范大學(xué)科學(xué)學(xué)報， 2002.18:26-27.
