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