中国剩余定理的背景及证明

毕业设计（论文）题目名称：中国剩余定理的背景及证明院系名称：理学院班级：数学与应用数学081班学号：学生姓名：指导教师：李旭红2012年4月中国剩余定理的背景及证明摘要本文主要讨论了中国剩余定理的背景、由来、证明方法以及一些简单的应用,文中阐述了中国剩余定理的由来，介绍了它的几种解法，及其它在多项式，现代密码学，生活方面的应用.“中国剩余定理”是由秦九韶从“孙子定理”的基础上推广而来的，本文从论述中国剩余定理的形成到中国剩余定理的主要方法和对现代教育的影响来写。中国剩余定理在高中有初步的基础应用，在大学中的初等数论中该定理得到了仔细的讲解。中国剩余定理的思想方法和原则不仅有光辉的历史意义，而且在近代数学中仍然有着重大影响和作用。关键词：中国剩余定理；证明；多项式；应用；影响THEBACKGROUNDANDPROOFOFTHECHINESEREMAINDERTHEOREMABSTRACTThispapermainlydiscussestheremaindertheoremofthebackgroundandorigin,andsomesimplewaystoprovetheapplication,thispaperexpoundstheoriginoftheChineseremaindertheoremisintroduced,andafewofitssolution,andotherinpolynomial,moderncryptography,theapplicationoflife.theChineseremaindertheoremisbyJiuShaoQinfromgrandsontheoreminthefoundationtopromote,thispaperdiscussestheformationoftheChineseremaindertheoremtoChineseremaindertheorem,themainmethodandmoderneducationtotheinfluenceofwriting.TheChineseremaindertheoreminhighschooltohaveapreliminaryfoundationapplication,theelementarytheoryinuniversityinthistheoremgotthesenseofthecarefully.TheChineseremaindertheoremmethodandprincipleofthoughtnotonlyaglorioushistorysignificance,andinmodernmathematicsstillhavesignificantinfluenceandfunction.Keywords:1引言中国剩余定理源于我国古代《孙子算经》,其中有一题:“今有物不知其数,三三数之剩二,五五数之剩三,七七数之剩二,问物几何？”这就是求解一次同余式组:)7(mod2)5(mod3)3(mod2xxx《孙子算经》中给出最小正整数解23,解法传至今世。中国剩余定理又称“孙子定理”。它数初等数论中重要定理之一，在代数数学和计算机领域中也有重要应用。本文主要讨论中国剩余定理的背景以及证明。2中国剩余定理的背景2.1中国剩余定理的由来在我国古代劳动人民中，长期流传着“隔墙算”、“剪管术”、“秦王暗点兵”等数学游戏。有一首“孙子歌”，甚至远渡重洋，输入日本：“三人同行七十稀，五树梅花廿一枝，七子团圆正半月，除百零五便得知。”这些饶有趣味的数学游戏，以各种不同形式，介绍世界闻名的“孙子问题”的解法，通俗地反映了中国古代数学一项卓越的成就。“孙子问题”在现代数论中是一个一次同余问题，它最早出现在我国公元四世纪的数学著作《孙子算经》中。《孙子算经》是算经十书之一，又作《孙子算术》。现有传本《孙子算经》分上、中、下共3卷。该书作者和确切成书年代均无法考证，大约成书于公元400年前后。中国古代求解一次同余式组（见同余）的方法。是数论中一个重要定理。又称中国剩余定理。一千多年前的《孙子算经》中，有这样一道算术题：“今有物不知其数，三三数之剩二，五五数之剩三，七七数之剩二，问物几何？”按照今天的话来说：一个数除以三余二，除以五余三，除以七余二，求这个数。《孙子算经》给出了一个非常有效的巧妙解法。术曰：“三、三数之剩二，置一百四十；五、五数之剩三，置六十三；七、七数之剩二，置三十，并之，得二百三十三。以二百一十减之，即得。凡三、三数之剩一，则置七十；五、五数之剩一，则置二十一；七、七数之剩一，则置十五。一百六以上，一百五减之，即得。在中国数学史上，广泛流传着一个“韩信点兵”的故事：韩信是汉高祖刘邦手下的大将，他英勇善战，智谋超群，为汉朝的建立立下了卓绝的功劳。据说韩信的数学水平也非常高超，他在点兵的时候，为了保住军事机密，不让敌人知道自己部队的实力，先令士兵从1至3报数，然后记下最后一个士兵所报之数；再令士兵从1至5报数，也记下最后一个士兵所报之数；最后令士兵从1至7报数，又记下最后一个士兵所报之数；这样，他很快就算出了自己部队士兵的总人数，而敌人则始终无法弄清他的部队究竟有多少名士兵？因为《孙子算经》对这类问题的研究只是初具雏形，还远远谈不上完整，其不足之处在于：（1）没有把解法总结成文，致使后人研究多凭猜测；（2）模数仅限于两两互质的正整数，未涉及一般情况；（3）未能进一步探究同余式（组）有解的条件等理论问题。因此，后人把这一命题及其解法成为“孙子定理”主要是推崇《孙子算经》在这一类问题的处理上时间领先，其实想方法的成熟，还有待提高。为了解决这一类“孙子问题”中的不足，秦九韶从孙子定理中推广了“孙子问题”的解法形成了“中国剩余定理”。秦九韶（秦九韶，字道古，生活于南宋时期，自幼喜好数学，经过长期积累和苦心钻研，干公元1247年写成《数书九章》。这部中世纪的数学杰作，在许多方面都有创造，其中求解一次同余组的“大衍求一术”和求高次方程数值解的“正负开方术”，更是具有世界意义的成就。秦九韶在《数书九章》中明确地系统地叙述了求解一次同余组的一般计算步骤。秦的方法，正是前述的剩余定理。）提出了乘率、定数、衍母、衍数等一系列数学概念，并详细叙述了“大衍求一术”的完整过程。直到此时，由《孙子算经》“物不知数”题开创的一次同余式问题，才真正得到了一个普遍的解法，才真正上升到了“中国剩余定理”的高度。这个故事中所说的韩信点兵的计算方法，就是现在被称为“中国剩余定理”的一次同余式解法。后来流传的《孙子歌》中所说“七十稀”、“廿一枝”和“正半月”，就是暗指这三个关键的数字。《孙子算经》没有说明这三个数的来历。实际上，它们具有如下特性：也就是说，这三个数可以从最小公倍数M=3×5×7=105中各约去模数3、5、7后，再分别乘以整数2、1、1而得到。假令k1=2，K2=1，K3=1，那么整数Ki（i=1，2，3）的选取使所得到的三数70、21、15被相应模数相除的时候余数都是1。由此出发，立即可以推出，在余数是R1、R2、R3的情况下的情况。应用上述推理，可以完全类似地把孙子算法推广到一般情形：设有一数N，分别被两两互素的几个数a1、a2、……an相除得余数R1、R2、……Rn，即N≡Ri（modai）（i=1、2、……n），只需求出一组数K，使满足1（modai）（i=1、2、……n），那么适合已给一次同余组的最小正数解是P是整数，M=a1×a2×……×an），就是现代数论中著名的剩余定理。为了比较清楚地了解“中国剩余定理”这一名称的由来，我们不妨先引进同余定义：般地,若两个整数a、b被同一个大于1的整数m除有相同的余数，那么称a、b对于模m同余.记作：)(modmba。应用同余原理，我们把“物不知其数”问题用整数的同余式符号表达出来是：设)7(mod2)5(mod3)3(mod2N，求最小的数N。答案是N=23。书中问题及其解法,建立起数学模型就是：设a、b、c为余数，P为整数。则)7(mod)5(mod)3(modcbaN的解是: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=å.我们把孙子的“物不知其数”问题的解法与高斯定理一对照,不难看出:高斯定理实质上就是孙子解法的推广.印度学者对一次同余论也有过重要贡献。从公元六世纪到十二世纪，他们发展了一种称为“库塔卡”的算法，用来求解和一次同余式等价的不定方程组。“库塔卡”法出现在孙子算法之后，印度数学家婆罗门复多（七世纪）、摩柯吠罗（九世纪）等人的著作中，都有和物不知数题相同的一次同余问题。这当然不是要借此断言“库塔卡”法一定受到了孙子算法的影响，但是有人（如万海依等）硬说中自的“大衍求一术”来源于“库塔卡”，就是毫无根据的妄说了。万海依居然把中国算法中数码从左到右横写作为“大衍术”受印度影响的重要根据。大家知道，中国古代至迟从春秋战国时期就开始使用算筹记数，我们今天还可以从现存的公元前三世纪的货币上看到这种从左到右的记数方法。由此可见，万海依的论点多么荒唐可笑。中国古代数学家对一次同余论的研究有明显的独创性和继承性，“大衍求一术”在世界数学史上的崇高地位是毋容置疑的，正因为这样，在西方数学史著作中，一直公正地称求解一次同余组的剩余定理为“中国剩余定理”。在中国,以剩余定理为代表的同余理论源远流长,可追溯到《周易》中的卜筮古法.秦九韶说:“圣有大衍,微寓于《易》”,即指此意.另外,同余理论的另一个来源是古代制定历法的需要.实际上,从汉末到宋末1000余年的时间中,有很多天文学家熟悉一次同余式的解法,他们在编制历法时利用它来推算“上元积年”.中国剩余定理对现代数学的研究有很强的启迪意义.特别是在多项式，密码学中的应用非常关键.随着数学学科的发展，数学方面的知识得到了不断的更新和强化。在数学发展史上，剩余问题（即：在整数除法里，一个数同时除以几个数，整数商后，均有剩余；已知各除数及其对应的余数，要求适合条件的这个被除数。这类问题统称剩余问题）曾经困扰过人们很长一段时间。这个问题的解决，是我们中国人迈出了开拓性的第一步。如果说，一部中国数学发展史像一条渊远流长的河流，那么几千年来祖先们取得的辉煌成就，就是这河流中耀眼的浪花。在祖先取得的成就中有一个“中国剩余定理”。大家都知道，“勾股定理”最早是由我国西周时期的商高发现的，但国外却称其为“毕达哥拉斯定理”，法国称为“驴桥定理”，埃及称为“埃及三角形”等。还有“增乘开方法”，最早是由我国宋代的贾宪发明的，但现代数学却称其为“霍纳法”，贾宪的发明比霍纳早了800年。而中国剩余定理则是唯一一个以我国国名命名的定理，大家一定对这个定理很感兴趣，很想知道关于这个定理的故事。现在我就为大家简单介绍一下“中国剩余定理”。公元1852年,英国基督教士伟烈亚力将《孙子算经》中的“物不知其数”问题的解法传到欧洲。公元1874年,马蒂生指出:孙子的解法完全符合高斯的定理。而此时,高斯定理已比《孙子算经》中的“物不知其数”问题的解法晚一千五百多年.从此,在西文的数学史上将“物不知其数”问题称为“中国剩余定理”或“孙子定理”.3中国剩余定理的证明及解法中国剩