浅析中国剩余定理及其应用

浅析中国剩余定理及其应用李辉（井冈山学院数理学院信息与计算科学343009）指导老师颜昌元[摘要]：本文阐述了中国剩余定理的由来，介绍了它的几种解法，及其它在多项式，现代密码学，生活方面的应用.[关键词]：中国剩余定理；解法;多项式；现代密码学引言在中国,以剩余定理为代表的同余理论源远流长,可追溯到《周易》中的卜筮古法.秦九韶说:“圣有大衍,微寓于《易》”,即指此意.另外,同余理论的另一个来源是古代制定历法的需要.实际上,从汉末到宋末1000余年的时间中,有很多天文学家熟悉一次同余式的解法,他们在编制历法时利用它来推算“上元积年”.中国剩余定理对现代数学的研究有很强的启迪意义.特别是在多项式，密码学中的应用非常关键.一中国剩余定理的由来我国古代《孙子算经》中有一著名而又重要的问题:“今有物不知其数,三三数之剩二、五五数之剩三,七七数之剩二,问物几何.答曰:二十三”.这一问题可译为:一个数除以3余2,除以5余3,除以7余2.求适合条件的最小的数.题中还介绍了它的解法:“术曰:三三数之剩二,置一百四十;五五数之剩三,置六十三;七七数之剩二,置三十;并之,得二百三十三,以二百十减之,即得.”意即:物数W=70×2+21×3+15×2-2×105=23.接下来又给出了这类题的一般解法(余数为一的情况):术文说:“凡三三数之剩一,则置七十;五五数之剩一,则置二十一;七七数之剩一,则置十五.一百六以上,以一百五减之,即得.”这个问题及其解法,在世界数学史上占有重要的地位,因此,中外数学家都尊称为“孙子定理”或“中国剩余定理”.为了比较清楚地了解“中国剩余定理”这一名称的由来,我们不妨先引进同余定义:一般地,若两个整数a、b被同一个大于1的整数m除有相同的余数,那么称a、b对于模m同余.记作:a≡b(modm）应用同余原理,我们把“物不知其数”问题用整数的同余式符号表达出来,是:设N≡2(mod3)≡3(mod5)≡2(mod7),求最小的数N.答案是N=23.书中问题及其解法,建立起数学模型就是:设a、b、c为余数,P为整数,则N≡a(mod3)≡b(mod5)≡c(mod7)的解是:N=70a+21b+15c-105P(1)现在,我们把上述解法中的a,b,c作一分析:设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(2)当时欧洲的数学家们对中国古代数学毫无所知.德国数学家高斯(1777~1855)通过独立研究,于公元1801年出版的《算术探究》上发表了著名的高斯定理:设123,,,,kaaaa为两两互质的h个除数,123,,,,kRRRR各为余数,123,,,,kMaaaa,1(mod)iNRa,1,2,3,,ih,如果我们找得到ik满足(mod)iika,那么1(mod)ihMiiaNkRM=å.我们把孙子的“物不知其数”问题的解法与高斯定理一对照,不难看出:高斯定理实质上就是孙子解法的推广.公元1852年,英国基督教士伟烈亚力将《孙子算经》中的“物不知其数”问题的解法传到欧洲。公元1874年,马蒂生指出:孙子的解法完全符合高斯的定理。而此时,高斯定理已比《孙子算经》中的“物不知其数”问题的解法晚一千五百多年.从此,在西文的数学史上将“物不知其数”问题称为“中国剩余定理”或“孙子定理”.二中国剩余定理的解法中国剩余定理的解法有许多，本文就介绍几种常见的，歌诀法，不定方程解法，同余解法。其余的解法就不一一介绍，每种解法有它的优点，最基础的还是歌诀法.2.1歌诀法2.1.1两个算数定理定理1被除数增加(或减少)除数的倍数,除数不变,则余数也不变.即:如果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被除数扩大(或缩小)几倍,除数不变,则余数也扩大(或缩小)同数倍.即:如果a÷b=q(余r),那么an÷b=qn(余rn);若rnb,则余rn-bm使rn-bmb(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解法歌诀明朝程大位编著的《算法统宗》(公元1592年)里记载了此题的解法,他是用一首歌谣(孙子歌)叙述出来的:“三人同行七十稀,五树梅花廿一枝,七子团圆正月半,除百零五便得知.”它的每句歌谣都隐藏着解题需要的数.“三(3)人同行七十(70)稀”,即用被3除所得的余数乘以70.“五(5)树梅花廿一(21)枝”,即用被5除所得的余数乘以21.“七(7)子团圆正月半(15)”,即用被7除所得的余数乘以15.“除百零五(105)便得知”,是说把上面所得的三个积相加,如果和大于105,就减去105的若干倍,直到差小于105为止,得出的差就是所求的最小正整数.解答算式是:70×2+21×3+15×2=233,233-105×2=232.1.3解法的理由及步骤①先在5与7的公倍数中找除以3余1的数,进而找到除以3余2的数.∵[5,7]=3535÷3=11(余2),由定理2(35×2)÷3=23(余1)而(70×2)÷3=46(余2),所以140是符合条件的数.②在3与7的公倍数中找除以5余3的数.∵[3,7]=2121÷5=4(余1)由定理221×3÷5=12(余3)即63符合条件③在3与5的公倍数中找除以7余2的数.∵[3,5]=1515÷7=2(余1)由定理215×2÷7=4(余2)即30符合条件④将上面得到的分别符合三个条件的三个数相加:70×2+21×3+15×2=233∵140加上的数都是3的倍数,∴除以3的余数不变(定理1);即233满足除以3余2的条件,同理可知,233也满足题目中的另外两个条件,即物数W=233就是本题的一个解,又∵[3,5,7]=105,再由定理1可知,233-2×105=23也是它的解,又∵23105,∴Wmin=23.上面的解法中,总是先求出余1的数,再求出余几的数,这种解法逐渐被总结为简洁实用的“求一术”.其实,早在宋朝的周密就曾把这个题目的解法编成如下的歌谣“三岁孩儿七十稀,五留廿一事尤奇,七度上元重相会,寒食清明便可知”.这里的“上元”指十五,而“寒食”指清明的前一天,冬至后106天是清明节,所以冬至到寒食为105天.歌谣中将解题所用各数暗暗给出,增加了题目的趣味性和神秘性.2.2.4不定方程解法设物数为W,W被3、5、7除所得的不完全商分别为x、y、z则有:W=3x+2(1)W=5y+3(2)(W,x,y,zN)W=7z+2(3)消去W,得到3x-5y=1(4)3x=7z(5)由(5)式得x=7z/3令13zt(1t∈N),得13zt17xt(6)从而有y=(211t-1)/5=4+(1t-1)/5,再令(1t-1)/5=2t(2t∈N)则1t=52t+1∴x=352t+7y=2t+4z=152t+3,W=1052t+23,这就是“物不知数”问题的通解公式,显然当2t=0时,有最小正整数解W=23.1.3同余解法“物不知数”问题用同余式组来表达,即W2(mod3)(1)W3(mod5)(2)W2(mod7)(3)解由(1)得W=123k(4)代入(2)式得123k≡3(mod5)31k≡1(mod5)31k≡6(mod5)1k≡2(mod5)1k=2+51k,将其代入(4)式有W=8+152k(5)由(5),(3)两式,8+152k=2(mod7)8+152k≡9(mod7)152k≡1(mod7)152k≡15(mod7)2k≡1(mod7)2k=1+73k,将2k代入(5)式,得W=23+1053k,即W=23(mod105)∵3、5、7两两互质,所以W≡23(mod105)是同余式组的解.在《孙子算经》中给出的解答实质上就是W≡70×2+21×3+15×2≡140+63+30≡233≡23(mod105)三中国剩余定理的应用中国剩余定理是我国古代数学家为世界数学发展作出的巨大贡献,它的数学思想在近代数学、当代密码学研究及日常生活都有着广泛应用.中国剩余定理：设123,,,,rmmmm是两两互素的正整数，设123,,,,raaaa是整数，则同余方程组(mod)iixam，1,2,3,,ir模123,,,,rMmmmm有惟一解1modriiiixaMyM,其中1/,modiiiiiMMmyMm,1,2,3,,ir.3.1中国剩余定理在多项式中的应用由中国剩余定理可得相似定理,设12(),(),,()nmxmxmx是n个两两互素的多项式,12(),(),()naxaxax是n个多项式,则一定存在多项式,使1122()()(mod())()()(mod())()()(mod())nnfxaxmxfxaxmxfxaxmx当f(s)的次数不超过12()(()()()())nmxmxmxmxmx的次数时,f(x)唯一确定.特别地,当()[]iimxxbQx（或[]Rx），i=1,2,…,n是互不相等的常数,从而()imx（i=1,2,…,n）也就是两两互素的多项式,由余数定iim()m()(mod())iixbxb,(i=1,2,…,n)从而定理可叙述为,一定存在多项式f(x),使111222()()(mod())()()(mod())()()(mod())nnnfxaxmxbfxaxmxbfxaxmxb其中()iax(i=1,2,…,n)是任意给定的常数,且多项式f(x)在次数不超过n的条件下是唯一确定的,由f(x)≡(mod())iiaxb等价于()iifba(i=1,2,…,n)得:对任意的互不相同的ib(i=1,2,…,n)及任意的ia(i=1,2,…,n)存在唯一的次数小于n的多项式f(x),使()iifba(i=1,2,…,n).这就是插值多项式的存在与唯一性定理.由中国剩余定理的证法,只要找到多项式()iMx(i=1,2,…,n),使()1(mod())iiMxxb()0(mod()),ijMxxbij而111111()()()()()()()()iiniiiiiinxbxbxbxbbbbbbbbb满足上式,于是得插值多项式f(x):112211()()()()()()()nninnjjijixbfxaMxaMxaMxaijbb这就是著名的Lagrange内插多项式.中国剩余定理推导出的内插多项式是处理许多多项式问题的基本工具,如简化数列求和问题:3.1.1计算2222012(1)n解假设和为n的三次多项式f(n),n代表项数,于是有f(0)=0,f(1)=0,f(2)=1,f(3)=5由插值公式得1234()0()0()1()5()fnMnMnMnMn(0)(1)(3)(0)(1)(2)5(20)(21)(23)(31)(30)(32)1(1)(21)6nnnnnnnnn所以,2222012(1)n=1(1)(21)6nnn3.1.2设f(x)以221,2xx的余式分别为4x+4,4x+8,求f(x)除以221,2xx的余式.解由条件可得f(x)≡4x+4(mod21x)f(x)≡4x+8(mod22x)注意到21x与22x互素,且(-1)·21x+1·22x=1,由上面及其证明可得f(x)≡(4x+4)·1·(22x)+(4x+8)·(-1)·(21x)(mod(21x)(22x),因此f(x)除以(21x)(22x)的余式为(4x+4)(22x)-(4x+8)(21x