中国剩余定理及其应用

INTELLIGENCE人文论坛212中国剩余定理及其应用郑州经贸职业学院刘明明郑州电子信息职业技术学院尚娟娟摘要：中国剩余定理又称为孙子定理，本文先给出该定理并进行证明，在此基础上对其在多种方面的一些基本应用进行初步的讨论和分析，并给出了相关的经典例题。关键词：中国剩余定理一次同余式组非互素模一、引言南北朝数学著作《孙子算经》中有题目“物不知其数”（参阅[1]）这样描述：“今有物，不知其数。三三数之，剩二；五五数之，剩三；七七数之，剩二；问物几何？”解法和答案用算式表示为702213152105223×+×+×−×=。即得到适合题意的昀小整数是23。“物不知其数”开创了一次同余式研究的先河，但真正从完整的计算程序和理论上解决这个问题的是南宋时期的数学家秦九韶，秦九韶在他的《数书九章》提出了一个数学方法“大衍求一术”。1876年，德国人马蒂生首先指出这一解法与19世纪高斯《算术探究》中关于一次同余式组的解法完全一致（参阅[2]）。从此，中国古代数学这一创造受到世界学者瞩目，并在西方数学史著中正式称为“中国剩余定理”。二、中国剩余定理设122,,,,nnmmm≥L两两互素的正整数，令121122nnnMmmmmMmMmM=====LL，则同余式组1122(mod)(mod)(mod)nnxcmxcmxcm=⎧⎪=⎪⎨⎪⎪=⎩LLLLLL有正整数解111222(mod)nnnxMcMcMcMααα≡+++L且解唯一；其中iα是满足1(mod),1,2,,)iiiMmknα≡=L的一个整数（参阅[3]）.下面我们先给出裴蜀恒等式和一个性质，然后证明中国剩余定理.裴蜀恒等式如果两个数的昀大公约数是d，则必定存在两个整数,xy使得等式axbyd+=成立（参阅[4]）.性质同余式组(mod),1,2,,jabmjn≡=L同时成立的充要条件是12(mod[,,,])nabmmm≡L（参阅[5]）.证明：先证存在性：因为12,,,nmmmL，两两互素，kkMMm=，故(,)1,1,2,,kkMmkn==L，由裴蜀恒等式可知一定存在整数,kkαβ使得1kkkkMmαβ+=，即1kkkkMmαβ=−+，因此必定存在kα，使1(mod),1,2,,kkkMmknα≡=L又因当kλ≠时，恒有kmMλ，所以1(mod)()kkMmkλαλ≡≠若令111222nnnRMcMcMcααα=+++L，则有11112222(mod)(mod)(mod)nnnnRMcmRMcmRMcmααα=⎧⎪=⎪⎨⎪⎪=⎩LLLLLLLL又kmM，故0(mod)kMm≡，从而(mod),1,2,,kkxRMtRcmkn=+≡≡=L.因此(mod)xRM≡，即111222(mod)nnnxMcMcMcMααα≡+++L为同余式组之解.唯一性：设该同余式组还有一解y，则有(mod),1,2,,kxymkn≡=L由于12,,,nmmmL两两互素，因此1212[,,,]nnMmmmmmm==LL，利用所给性质可知(mod)xyM≡，证毕.三、中国剩余定理的应用1、在同余式组中的应用例“韩信点兵”的问题（参阅[6]）：有兵一队，若列成五行纵列则末行一人；成六行纵队，则末行五人；成七行纵队，则末行四人；成十一行纵队，则末行十人，求兵数.解：“韩信点兵”问题转化为数学语言即求解下列一次同余式组1(mod5)5(mod6)4(mod7)10(mod11)xxxx≡⎧⎪≡⎪⎨≡⎪⎪≡⎩按照中国属于定理的记号12567112310,6711462,5711385,MMM=×××==××==××=345611330,567210,MM=××==××=又要求1(mod),1,2,3,4,iiiMmiα⋅≡=得12343,1,αααα====又12341,5,4,10,cccc====于是111222333444(mod)xMcMcMcMcMαααα≡+++462313851533014210110(mod2310)≡××+××+××+××1386192513202100(mod2310)≡+++6731(mod2310)≡2111(mod2310)≡即韩信的兵有21112310,kk+为非负整数2、在数学奥林匹克中的应用定义没有重复因子的数称为无乘方数；比如1535=×是无乘方数，而21223=×则不是.例(1986)USAMO是否存在21个连续的正整数，其中每一个数均至少可被一个不小于2且不大于13的素数整除？分析：如果n可以被2102357=×××整除，那么对于21个连续整数n-10,n-9,,n+9,n+10L中除去1n+，1n−这两个数，当1n−可被11整除，同时1n+可被13整除（或者反过来）时，于是我们就得到所求的21个连续整数了.解：依上面的分析，只要n满足0(mod210)1(mod11)1(mod13)nnn≡⎧⎪≡⎨⎪=−⎩INTELLIGENCE人文论坛213就得到所求的数列了，为完整起见，那么来求这一同余组的解.注意，210n=满足前两个同余式，于是对任意的k只要令21011210nk=××+满足昀后一个同余式，选取k使得210112310211(mod13)kk××=≡−，此式化简为93(mod13)k≡−而4k=是显然是解了，于是423102109450n=×+=是一个解（昀小正解）而945030030nm=+是一般解，其中m是任意的整数.3、在多项式中的应用中国剩余定理在多项式中的应用是比较广泛的，其中Lagrange内插多项式是处理许多多项式问题的基本工具；下面我们通过余数定理和插值多项式的存在和唯一性定理导出Lagrange内插多项式，再通过Lagrange内插多项式求一级数的和.（1）余数定理余数定理是指一个多项式()fx除以一线性多项式xa−的余数是()fa.（2）插值多项式的存在和唯一性定理设12(),(),,()nmxmxmxL是n个两两互素的多项式，12(),(),,()naxaxaxL是n个多项式，而一定存在多项式()fx，使1122nnf(x)(x)(modm(x))f(x)(x)(modm(x))f(x)(x)(modm(x))aaa≡⎧⎪≡⎪⎨⎪⎪≡⎩LLLLLLLLLL当()fx的次数不超过123()(()()()()())nMxMxmxmxmxmx=L的次数时，()fx唯一确定.特别地，当()[][]iimxxbQxRx=−∈或，(1,2,,)ibin=L是不相等的常数，从而()(1,2,,)imxin=L也就是两两互素的多项式，由余数定理可知()()(mod),(1,2,,)iiiimxmbxbin≡−=L，从而定理可叙述为一定存在多项式()fx，使得1122nnf(x)(modx-b)f(x)(modx-b)f(x)(modx-b)aaa≡⎧⎪≡⎪⎨⎪⎪≡⎩LLLLLLLL其中(1,2,,)iain=L是任意给定的常数，且多项式()fx在次数不超过n的条件下是唯一确定的.由()(mod)iifxaxb≡−等价于()(1,2,,)iifbain==L知对任意的互不相同的(1,2,,)ibin=L及任意的(1,2,,)iain=L，存在唯一的次数小于n的多项式()fx，使()(1,2,,)iifbain==L，这就是插值多项式的存在和唯一性定理.（3）Lagrange内插多项式1122()()()()nnfxaMxaMxaMx=+++L11()()()nnijjijixbaijbb==−=≠−∑∏其中，111111()()()()()()()()()iiniiiiiiinxbxbxbxbMxbbbbbbbb−+−+−−−−=−−−−LLLL(1,2,,)in=L是n个两两互素的多项式，(1,2,,)ibin=L是不相等的常数，(1,2,,)iain=L是任意给定的常数.分析：根据插值多项式的存在和唯一性定理，由中国剩余定理的证法，只要找到多项式()(1,2,,)iMxin=L，使()1(mod)()0(mod),iiijMxxbMxxbij≡−⎧⎪⎨≡−≠⎪⎩而111111()()()()()()()()()iiniiiiiiinxbxbxbxbMxbbbbbbbb−+−+−−−−=−−−−LLLL(1,2,,)in=L符合要求，于是插值多项式1122()()()()nnfxaMxaMxaMx=+++L11()()()nnijjijixbaijbb==−=≠−∑∏即所求.例利用内插多项式简化下列数列求和问题，2222012(1)n++++−L解：设和为n的三次多项式()fn，n代表项数，于是有(0)0,(1)1,(2)1,(3)5ffff====由插值公式得1234()0()0()1()5()fnMnMnMnMn=×+×+×+×(0)(1)(3)(0)(1)(2)5(20)(21)(23)(30)(31)(32)nnnnnn−−−−−−=+×−−−−−−1(1)(21)6nnn=−−所以2222012(1)n++++−LL1(1)(21)6nnn=−−4、在生活中的应用在日常生活中我们所注意到的不是某些数，而是这些数去除某一固定的数所得到的余数.例如，假定现在是早上10点，在两个小时前是几点？我们立刻可得到正确答案是早上8点那么过了13个小时后又是几点呢？算式为10+13-12=11即晚上11点；在28个小时后手表的时针又是什么情况呢？算式为(10+28)-(123)=2×即是两点.解决此类问题的方法是：若现在的时间是A，问经过B小时后的时间，只需计算(mod12)ABc+≡，余数就是手表的时针数.5、在其他方面的应用其实，中国剩余定理主要是解决一次同余式组的问题，在当代密码学中也得到应用。目前人们已经可以用计算机，通过编程，实现对求一次同余式组的算法自动化，而对于模非两两互素的情况，通过对中国剩余定理的推广(参阅[7])，冯国锋对此方案进行了研究和改进。[8]此外，中国剩余定理在赋值理论中亦得到一定的应用（参阅[9]），在曲面拼接中的应用（参阅[10]）随着计算机技术的发展也变得更加广泛。四、结束语本文通过对中国剩余定理的描述阐述，对中国剩余定理（孙子定理）在实际生活中的应用进行了初步的说明和描述。以上只是一些简单的例子，但足可见中国剩余定理应用之广泛，地位之高，作为数学史上名垂百世的成就，其数学思想一直启发和指引着历代数学家。参考文献：[1]纪志刚编：《孙子算经》，《张邱键算经》，《夏侯阴算经导读》，湖北教育出版社，1999年。[2][A]KennthRosenK.H.ElementaryNunberTheoryandItsApplications.FifthEditon[M].Beijing:ChinaMachinePress:158-168.[3]晏能中著：《初等数论》，电子科技大学出版社，2005年。[4]潘承洞、潘承虎：《简明数论》，北京大学出版社，2001年。[5]冯国锋：《广义中国剩余定理及其Maple解法》，重庆大学学报（自），2004年。