我国剩余定理的背景与证明

1、 15/15 毕业设计（论文）题目名称：中国剩余定理的背景及证明院系名称：理学院班 级：数学与应用数学081班学 号：学生某：指导教师：李旭红 2012年4月中国剩余定理的背景及证明摘 要本文主要讨论了中国剩余定理的背景、由来、证明方法以及一些简单的应用, 文中阐述了中国剩余定理的由来，介绍了它的几种解法，及其它在多项式，现代密码学，生活方面的应用.“中国剩余定理”是由秦九韶从“孙子定理”的基础上推广而来的，本文从论述中国剩余定理的形成到中国剩余定理的主要方法和对现代教育的影响来写。中国剩余定理在高中有初步的基础应用，在大学中的初等数论中该定理得到了仔细的讲解。中国剩余定理的思想方法和原则不仅

2、有光辉的历史意义，而且在近代数学中仍然有着重大影响和作用。关键词：中国剩余定理； 证明；多项式；应用；影响THE BACKGROUND AND PROOF OFTHE CHINESE REMAINDER THEOREMABSTRACTThis paper mainly discusses the remainder theorem of the background and origin, and some simple ways to prove the application, this paper expounds the origin of the Chinese remainder

3、theorem is introduced, and a few of its solution, and other in polynomial, modern cryptography, the application of life. the Chinese remainder theorem is by JiuShaoQinfrom grandson theorem in the foundation to promote, this paper discusses the formation of the Chinese remainder theorem to Chinese re

4、mainder theorem, the main method and modern education to the influence of writing. The Chinese remainder theorem in high school to have a preliminary foundation application, the elementary theory in university in this theorem got the sense of the carefully. The Chinese remainder theorem method and p

5、rinciple of thought not only a glorious history significance, and in modern mathematics still have significant influence and function. Keywords:1 引言中国剩余定理源于我国古代孙子算经, 其中有一题: “ 今有物不知其数, 三三数之剩二, 五五数之剩三, 七七数之剩二, 问物几何？” 这就是求解一次同余式组: 孙子算经中给出最小正整数解, 解法传至今世。中国剩余定理又称“孙子定理”。它数初等数论中重要定理之一，在代数数学和计算机领域中也有重要应用。本文

6、主要讨论中国剩余定理的背景以及证明。 2 中国剩余定理的背景2.1中国剩余定理的由来在我国古代劳动人民中，长期流传着“隔墙算”、“剪管术”、“秦王暗点兵”等数学游戏。有一首“孙子歌”，甚至远渡重洋，输入日本：“三人同行七十稀，五树梅花廿一枝，七子团圆正半月，除百零五便得知。” 这些饶有趣味的数学游戏，以各种不同形式，介绍世界闻名的“孙子问题”的解法，通俗地反映了中国古代数学一项卓越的成就。“孙子问题”在现代数论中是一个一次同余问题，它最早出现在我国公元四世纪的数学著作孙子算经中。孙子算经是算经十书之一，又作孙子算术。现有传本孙子算经分上、中、下共3卷。该书作者和确切成书年代均无法考证，大约成书

7、于公元400年前后。中国古代求解一次同余式组（见同余）的方法。是数论中一个重要定理。又称中国剩余定理。一千多年前的孙子算经中，有这样一道算术题：“今有物不知其数，三三数之剩二，五五数之剩三，七七数之剩二，问物几何？”按照今天的话来说：一个数除以三余二，除以五余三，除以七余二，求这个数。孙子算经给出了一个非常有效的巧妙解法。术曰：“三、三数之剩二，置一百四十；五、五数之剩三，置六十三；七、七数之剩二，置三十，并之，得二百三十三。以二百一十减之，即得。凡三、三数之剩一，则置七十；五、五数之剩一，则置二十一；七、七数之剩一，则置十五。一百六以上，一百五减之，即得。 在中国数学史上，广泛流传着一个“韩

8、信点兵”的故事：韩信是汉高祖X邦手下的大将，他英勇善战，智谋超群，为汉朝的建立立下了卓绝的功劳。据说韩信的数学水平也非常高超，他在点兵的时候，为了保住军事某，不让敌人知道自己部队的实力，先令士兵从1至3报数，然后记下最后一个士兵所报之数；再令士兵从1至5报数，也记下最后一个士兵所报之数；最后令士兵从1至7报数，又记下最后一个士兵所报之数；这样，他很快就算出了自己部队士兵的总人数，而敌人则始终无法弄清他的部队究竟有多少名士兵？因为孙子算经对这类问题的研究只是初具雏形，还远远谈不上完整，其不足之处在于：（1）没有把解法总结成文，致使后人研究多凭猜测；（2）模数仅限于两两互质的正整数，未涉及一般情况

9、；（3） 未能进一步探究同余式（组）有解的条件等理论问题。因此，后人把这一命题及其解法成为“孙子定理”主要是推崇孙子算经在这一类问题的处理上时间领先，其实想方法的成熟，还有待提高。为了解决这一类“孙子问题”中的不足，秦九韶从孙子定理中推广了“孙子问题”的解法形成了“中国剩余定理”。 秦九韶（秦九韶，字道古，生活于南宋时期，自幼喜好数学，经过长期积累和苦心钻研，干公元1247年写成数书九章。这部中世纪的数学杰作，在许多方面都有创造，其中求解一次同余组的“大衍求一术”和求高次方程数值解的“正负开方术”，更是具有世界意义的成就。秦九韶在数书九章中明确地系统地叙述了求解一次同余组的一般计算步骤。秦的方

10、法，正是前述的剩余定理。）提出了乘率、定数、衍母、衍数等一系列数学概念，并详细叙述了“大衍求一术”的完整过程。直到此时，由孙子算经“物不知数”题开创的一次同余式问题，才真正得到了一个普遍的解法，才真正上升到了“中国剩余定理”的高度。 这个故事中所说的韩信点兵的计算方法，就是现在被称为“中国剩余定理”的一次同余式解法。后来流传的孙子歌中所说“七十稀”、“廿一枝”和“正半月”，就是暗指这三个关键的数字。孙子算经没有说明这三个数的来历。实际上，它们具有如下特性：也就是说，这三个数可以从最小公倍数M=357=105中各约去模数3、5、7后，再分别乘以整数2、1、1而得到。假令k1=2，K2=1，K3=

11、1，那么整数Ki（i=1，2，3）的选取使所得到的三数70、21、15被相应模数相除的时候余数都是1。由此出发，立即可以推出，在余数是R1、R2、R3的情况下的情况。应用上述推理，可以完全类似地把孙子算法推广到一般情形：设有一数N，分别被两两互素的几个数a1、a2、an相除得余数R1、R2、Rn，即NRi（mod ai）（i=1、2、n），只需求出一组数K，使满足1（mod ai）（i=1、2、n），那么适合已给一次同余组的最小正数解是P是整数，M=a1a2an），就是现代数论中著名的剩余定理。为了比较清楚地了解“中国剩余定理”这一名称的由来，我们不妨先引进同余定义：般地,若两个整数a、b被同

12、一个大于1的整数m除有相同的余数，那么称a、b对于模m同余.记作：。应用同余原理，我们把“物不知其数”问题用整数的同余式符号表达出来是：设，求最小的数N。答案是N=23。书中问题及其解法,建立起数学模型就是：设a、b、c为余数， P为整数。则的解是: N=70a+21b+15c-105P (1)现在,我们把上述解法中的a,b,c作一分析:设M=357,则 70=257=2(357)/3=2M/321=37=1(357)/5=1M/515=37=1(357)/7=1M/7因此,问题的解(1)式可以写成: N=2M/3a+1M/5b+1M/7c (2)当时欧洲的数学家们对中国古代数学毫无所知.德国

13、数学家高斯(17771855)通过独立研究,于公元1801年出版的算术探究上发表了著名的高斯定理:设为两两互质的h个除数, 各为余数, , ,如果我们找得到满足,那么.我们把孙子的“物不知其数”问题的解法与高斯定理一对照,不难看出:高斯定理实质上就是孙子解法的推广.印度学者对一次同余论也有过重要贡献。从公元六世纪到十二世纪，他们发展了一种称为“库塔卡”的算法，用来求解和一次同余式等价的不定方程组。“库塔卡”法出现在孙子算法之后，印度数学家婆罗门复多（七世纪）、摩柯吠罗（九世纪）等人的著作中，都有和物不知数题相同的一次同余问题。这当然不是要借此断言“库塔卡”法一定受到了孙子算法的影响，但是有人（

14、如万海依等）硬说中自的“大衍求一术”来源于“库塔卡”，就是毫无根据的妄说了。万海依居然把中国算法中数码从左到右横写作为“大衍术”受印度影响的重要根据。大家知道，中国古代至迟从春秋战国时期就开始使用算筹记数，我们今天还可以从现存的公元前三世纪的货币上看到这种从左到右的记数方法。由此可见，万海依的论点多么荒唐可笑。中国古代数学家对一次同余论的研究有明显的独创性和继承性，“大衍求一术”在世界数学史上的崇高地位是毋容置疑的，正因为这样，在西方数学史著作中，一直公正地称求解一次同余组的剩余定理为“中国剩余定理”。在中国,以剩余定理为代表的同余理论源远流长,可追溯到周易中的卜筮古法.秦九韶说:“圣有大衍,

15、微寓于易”,即指此意.另外,同余理论的另一个来源是古代制定历法的需要.实际上,从汉末到宋末1000余年的时间中,有很多天文学家熟悉一次同余式的解法,他们在编制历法时利用它来推算“上元积年”.中国剩余定理对现代数学的研究有很强的启迪意义.特别是在多项式，密码学中的应用非常关键. 随着数学学科的发展，数学方面的知识得到了不断的更新和强化。在数学发展史上，剩余问题（即：在整数除法里，一个数同时除以几个数，整数商后，均有剩余；已知各除数及其对应的余数，要求适合条件的这个被除数。这类问题统称剩余问题）曾经困扰过人们很长一段时间。这个问题的解决，是我们中国人迈出了开拓性的第一步。如果说，一部中国数学发展史

16、像一条渊远流长的河流，那么几千年来祖先们取得的辉煌成就，就是这河流中耀眼的浪花。在祖先取得的成就中有一个“中国剩余定理”。大家都知道，“勾股定理”最早是由我国西周时期的商高发现的，但国外却称其为“毕达哥拉斯定理”，法国称为“驴桥定理”，埃及称为“埃及三角形”等。还有“增乘开方法”，最早是由我国宋代的贾宪发明的，但现代数学却称其为“霍纳法”，贾宪的发明比霍纳早了800年。而中国剩余定理则是唯一一个以我国国名命名的定理，大家一定对这个定理很感兴趣，很想知道关于这个定理的故事。现在我就为大家简单介绍一下“中国剩余定理”。 公元1852年,英国基督教士伟烈亚力将孙子算经中的“物不知其数”问题的解法传到

17、欧洲。公元1874年,马蒂生指出:孙子的解法完全符合高斯的定理。而此时,高斯定理已比孙子算经中的“物不知其数”问题的解法晚一千五百多年.从此,在西文的数学史上将“物不知其数”问题称为“中国剩余定理”或“孙子定理”.3中国剩余定理的证明及解法中国剩余定理：设是两两互素的正整数，设是整数，则同余方程组，模有惟一解 ,其中,.3.1中国剩余定理的解法中国剩余定理的解法有许多，本文就介绍几种常见的，歌诀法，不定方程解法，同余解法。其余的解法就不一一介绍，每种解法有它的优点，最基础的还是歌诀法.2.1 歌诀法2.1.1 两个算数定理定理1被除数增加(或减少)除数的倍数,除数不变,则余数也不变.即:如果a

18、b=q (余r),则(a+bn)b=q+n (余r) (nZ).证明ab=q (余r)则a=bq+ra+bn =(q+n)b+r,即(a+bn),b=q+n(余r)定理2被除数扩大(或缩小)几倍,除数不变,则余数也扩大(或缩小)同数倍.即:如果ab=q (余r),那么anb=qn (余rn);若rnb,则余rn-bm使rn-bmb (m, nZ),则: anb=qn+m (余rn-bm)证明由ab=q (余r) a=bq+r,则an=b (nq)+rn,所以anb=nq (余rn)2.1.2解法歌诀明朝程大位编著的算法统宗(公元1592年)里记载了此题的解法,他是用一首歌谣(孙子歌)叙述出来的

19、:“三人同行七十稀,五树梅花廿一枝,七子团圆正月半,除百零五便得知.”它的每句歌谣都隐藏着解题需要的数.“三(3)人同行七十(70)稀”,即用被3除所得的余数乘以70.“五(5)树梅花廿一(21)枝”,即用被5除所得的余数乘以21.“七(7)子团圆正月半(15)”,即用被7除所得的余数乘以15.“除百零五(105)便得知”,是说把上面所得的三个积相加,如果和大于105,就减去105的若干倍,直到差小于105为止,得出的差就是所求的最小正整数.解答算式是:702+213+152=233,233-1052=232.1.3解法的理由及步骤先在5与7的公倍数中找除以3余1的数,进而找到除以3余2的数.

20、5, 7=35353=11(余2),由定理2(352)3=23(余1) 而(702)3=46(余2),所以140是符合条件的数.在3与7的公倍数中找除以5余3的数.3,7=21215=4(余1)由定理22135=12(余3)即63符合条件在3与5的公倍数中找除以7余2的数.3,5=15157=2(余1)由定理21527=4(余2)即30符合条件将上面得到的分别符合三个条件的三个数相加:702+213+152=233140加上的数都是3的倍数,除以3的余数不变(定理1);即233满足除以3余2的条件,同理可知,233也满足题目中的另外两个条件,即物数W=233就是本题的一个解,又3,5,7=10

21、5,再由定理1可知,233-2105=23也是它的解,又23105,Wmin=23.上面的解法中,总是先求出余1的数,再求出余几的数,这种解法逐渐被总结为简洁实用的“求一术”.其实,早在宋朝的周密就曾把这个题目的解法编成如下的歌谣“三岁孩儿七十稀,五留廿一事尤奇,七度上元重相会,寒食清明便可知”.这里的“上元”指十五,而“寒食”指清明的前一天,冬至后106天是清明节,所以冬至到寒食为105天.歌谣中将解题所用各数暗暗给出,增加了题目的趣味性和神秘性.2.2.4不定方程解法设物数为W, W被3、5、7除所得的不完全商分别为x、y、z则有:消去W,得到 3x-5y=1 (4) 3x=7z (5)由

22、(5)式得x=7z/3令 (N),得 (6)从而有y=(21-1)/5=4+(-1)/5, 再令(-1)/5= (N)则=5+1x=35+7y=+4z=15+3,W=105+23,这就是“物不知数”问题的通解公式,显然当=0时,有最小正整数解W=23.1.3同余解法“物不知数”问题用同余式组来表达,即解由(1)得W= (4)代入(2)式得3(mod5) 31 (mod5) 36(mod5) 2(mod5) =2+5,将其代入(4)式有W=8+15 (5)由(5),(3)两式,8+15=2(mod7)8+159(mod7)151(mod7)1515(mod7) 1(mod7) =1+7,将代入(

23、5)式,得W=23+105,即W=23(mod105)3、5、7两两互质,所以W23(mod105 )是同余式组的解.在孙子算经中给出的解答实质上就是W702+213+152140+63+3023323(mod105)3.2中国剩余定理的证明设 12 2, , , ,n nmm m L 两两互素的正整数，令 12 1 1 2 2 nnn Mmm m mM mM mM = LL ，则同余式组 1122(mod )(mod )(mod ) nnxc mxc mxc m= = = LLLLLL有正整数解 111 2 22 (mod ) nnn xMcM c M c M + + L 且解唯一；其中 i

24、 是满足 1(mod ), 1, 2, , ) ii iMmkn = L 的一个整数（参阅 3）.下面我们先给出裴蜀恒等式和一个性质，然后证明中国剩余定理 .裴蜀恒等式 如果两个数的最大公约数是d ，则必定存在两个整数 , xy使得等式ax by d += 成立（参阅 4）.性质 同余式组 (mod ), 1, 2, ,jab m j n = L 同时成立的充要条件是 12 (mod , , , ) n ab mm m L （参阅 5）.证明： 先证存在性：因为 12 ,n mm m L ，两两互素， kkM M m= ，故(,)1, 1,2,kkMm k n = L ，由裴蜀恒等式可知一定存

25、在整数 ,kk 使得1 kk k kMm += ，即 1 kk k kMm = + ，因此必定存在 k ，使1(mod ), 1, 2, ,kk kMmkn = L又因当 k 时，恒有 kmM ，所以 1(mod )( ) kkMmk 若令 111 2 22 nnn RMcM c M c =+ + L ，则有111 1222 2(mod )(mod )(mod ) nnn nRMc mRM c mRM c m= = = LLLLLLLL又 kmM ，故 0(mod ) kMm ，从而(mod ), 1, 2, ,kkxRMtRc mk n =+ = L .因此 (mod ) xR M ，即 1

26、11 2 22 (mod ) nnn xMcM c M c M + + L 为同余式组之解 .唯一性：设该同余式组还有一解 y，则有(mod ), 1, 2, ,kxy mk n = L由于 12 ,n mm m L 两两互素，因此 12 12 , , nn Mmm m mmm = LL ，利用所给性质可知 (mod ) xy M ，证毕 .4中国剩余定理的应用中国定理是中国古代数学家为世界数学发展作出的巨大贡献, 它的数学思想在近代数学、当代秘密学研究及日常生活都有着广泛应用. 4. 1中国剩余定理在赋值理论中的体现 赋值理论是域论的一个分支, 是研究近代数学中几个重要分支如代数数论、交换数

27、论的一个重要工具, 而中国剩余定理在赋值论中起着重要作用, 下面介绍中国剩余定理在赋值理论中的应用. 定理 (赋值的独立性)对于任意个赋值, , , 以及任意, , 则存在使; (2), 证明 设为的最小公分母, 令, , , . 根据中国剩余定理, 可求得一个, 使得, , , 即 , 设, 取适当的, 使, 再令, 则显然满足条件(1). 又由距离的性质: 有, . 4. 2 中国剩余定理在多项式中的应用 由中国剩余定理可得相似定理. 设是个两两互素的多项式, 是个多项式, 则一定存在多项式, 使当的次数不超过的次数是, 唯一确定. 特别地, 当(或), , 是互不相等的常数, 从而也是两两互素的多项式, 由余数定理可知, 从而定理可叙述为, 一定存在多项式, 是其中是任意给定的常数, 且多项式在次数不超过的条件下唯一确定的, 有等价于得: 对任意互不相同的存在唯一的次数小于的多项式, 是. 这就是插值多项式的存在与唯一性定理. 由中国剩余定理的证法, 只要找到多项式, 使, (1)而满足(1), 于是的插值多项式: 这就是著名的Lagrange内插多项式. 中国剩余定理推导出的内插多项式是处理许多多项式问题的基本工具如简化数列求和问题: 计算解 假设和为的三次多项式, 代表项数, 于是有由插值公式得所以, .中国剩余定理主要是解决一次同余式问题, 在算术中还可以利用它来