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

《浅析中国剩余定理及其应用》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、浅析中国剩余定理及其应用李辉（井冈山学院数理学院信息与计算科学343009）指导老师颜昌元[摘要]：本文阐述了中国剩余定理的由来，介绍了它的几种解法，及其它在多项式，现代密码学，生活方面的应用.[关键词]：中国剩余定理；解法;多项式；现代密码学引言在中国,以剩余定理为代表的同余理论源远流长,可追溯到《周易》中的卜筮古法.秦九韶说:“圣有大衍,微寓于《易》”,即指此意.另外,同余理论的另一个来源是古代制定历法的需要.实际上,从汉末到宋末1000余年的时间中,有很多天文学家熟悉一次同余式的解法,他们在编制历法时利用它来推算“上元积年”.中国剩余定理对现代数学的研究有

2、很强的启迪意义.特别是在多项式，密码学中的应用非常关键.一中国剩余定理的由来我国古代《孙子算经》中有一著名而又重要的问题:“今有物不知其数,三三数之剩二、五五数之剩三,七七数之剩二,问物几何.答曰:二十三”.这一问题可译为:一个数除以3余2,除以5余3,除以7余2.求适合条件的最小的数.题中还介绍了它的解法:“术曰:三三数之剩二,置一百四十;五五数之剩三,置六十三;七七数之剩二,置三十;并之,得二百三十三,以二百十减之,即得.”意即:物数W=70×2+21×3+15×2-2×105=23.接下来又给出了这类题的一般解法(余数为一的情况):术文说:“凡三三数之剩一

3、,则置七十;五五数之剩一,则置二十一;七七数之剩一,则置十五.一百六以上,以一百五减之,即得.”这个问题及其解法,在世界数学史上占有重要的地位,因此,中外数学家都尊称为“孙子定理”或“中国剩余定理”.为了比较清楚地了解“中国剩余定理”这一名称的由来,我们不妨先引进同余定义:一般地,若两个整数a、b被同一个大于1的整数m除有相同的余数,那么称a、b对于模m同余.记作:a≡b(modm）应用同余原理,我们把“物不知其数”问题用整数的同余式符号表达出来,是:设N≡2(mod3)≡3(mod5)≡2(mod7),求最小的数N.答案是N=23.书中问题及其解法,建立起数学

4、模型就是:设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年出版的《算术探究》上发表

5、了著名的高斯定理:设为两两互质的h个除数,各为余数,,,,如果我们找得到满足,那么.我们把孙子的“物不知其数”问题的解法与高斯定理一对照,不难看出:高斯定理实质上就是孙子解法的推广.公元1852年,英国基督教士伟烈亚力将《孙子算经》中的“物不知其数”问题的解法传到欧洲。公元1874年,马蒂生指出:孙子的解法完全符合高斯的定理。而此时,高斯定理已比《孙子算经》中的“物不知其数”问题的解法晚一千五百多年.从此,在西文的数学史上将“物不知其数”问题称为“中国剩余定理”或“孙子定理”.二中国剩余定理的解法中国剩余定理的解法有许多，本文就介绍几种常见的，歌诀法，不定方程解

6、法，同余解法。其余的解法就不一一介绍，每种解法有它的优点，最基础的还是歌诀法.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);若rn>b,则余rn-bm使rn-bm

7、余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)便得知”,是说把上面所得的

8、三个积相加,如果和大于1