欧几里得算法在历史上的不同呈现.doc

欧几里得算法在历史上的不同呈现二 国外的欧几里得算法2.1 几何原本中的欧几里得算法2.11 欧几里得和他的几何原本 欧几里得（Eudides 或 Eucleides，公元前三百年前后），是希腊数学家。欧几里得的几何原本是一部划时代的著作。中国传统数学的最大特点是以算为中心，没有形成如同古希腊数学那样的公理化体系。几何原本开创了数学公理化的正确道路，促进了整个数学的发展。几何原本全书共由十三卷组成，第一卷到第六卷为平面几何学，它是由徐光启，利玛窦在1607年共同译完，明末传入我国，补救我国数学研究中的不足。第七卷到第十卷为数论，但与中算不同的是，全用几何方式来叙述。其中第卷命题就是用几何方式来叙述欧几里得算法。第十一卷到第十三卷为立体几何学。早在半个世纪以前，日本数学家小仓金之助把九章算术与几何原本进行比较，他认为九章算术是“中国的欧几里得”，作为东西方数学的代表作，九章算术与几何原本在数学发展史上的产生和流传有相似之处。欧几里得算法来源于几何原本，但欧几里得算法中算法思想却与古印度，日本，意大利，德国，以及我国古代现代许多数学研究一致。2.12欧几里得算法几何原本第卷命题中原文如下“设有不相等的二数，若依次从大数中不断地减去小数，若余数总是量不尽它前面的一个数，直到最后的余数为一个单位，则该二数互素”。命题二中“已知两个不互素的数，求它们的最大公度数。 术文如下 设 AB,CD是不互素的两数，求 AB,CD 的最大公度数。如果 CD 量尽AB ，那么它也能量尽它自己，那么 CD 就是CD,AB 的最大公度数。且显然CD 也是最大公度数，这是因为没有比CD大的数能量尽CD ，但是，如果CD量不尽AB，那么从AB,CD 中的较大者中不断地减去较小者，如此，将有某个余数能量尽它前面的一个。这最后的余数不是一个单位，否则AB,CD 就是互素的。”2.2印度的不定方程组问题一次不定分析在中国，印度，古希腊数学中多有研究，特别是对印度数学家来说是非常重要的。他们非常重视一次不定分析的研究，曾一度用它来代表这门学科。2.3日本数学家关孝和的叙述据相关文献考证，日本数学发展是从钱明天皇时代开始的，历史记载公元554年百济有历法博士到日本传授历法。602年又有和尚关勒到日本传授天文知识。说明我国数学天文成果以朝鲜为跳板在公元六世纪已经传入日本。日本数学在发展中逐渐形成独特的体系，称为和算。日本被誉为和算之圣的数学家关孝和是数学家毛利的再传弟子。关孝和在解同余式问题中所拟题及其解法是深透的，特别是他的剩一术对秦九韶大衍求一术中划一程序的解释比黄宗宪要早一百多年。2.31关孝和解同余式19x=1(mod 27)关孝和用汉文写的括要算法卷二有剩一术，是用更想减损的方法计算同余式ax=1(mod b)的解。原文如下“今有以左一十九累加之得数，以右二十七累减之，剩一，问左总数几何？答：左总数190。”可以看出上文是解同余式19x=1(mod 27)的问题。关孝和在解题术文中所说的解题程序如下“以左一十九，除右二十七，得商一，不尽（余数）八为甲。以甲不尽八，除左一十九，得商二，不尽三，为乙。以乙不尽三除甲，不尽八，得商二，不尽三，为丙。以丙不尽二除乙，不尽三，得商一，不尽一， 为丁，乃余一而止。”转换成图示为紧接着还有四句术文如下“甲商与乙商相因，加定一，得三为子。子与丙商相因，加甲商，得七为丑。丑与丁商相因，加子，得一十。以左一十九乘之，得左总数一百九十，合问。”转换成数学语言为2.32关孝和解同余式组关孝和对解同余式组问题也作了深入研究。在括要算法卷二“剪管术”中自拟辅助题“今有物不知其数，只云五除余一个，七除余二个，问总数几何。”答数为十六个。这就是解同余式组关孝和作出术文“五余以二十一乘得二十一个，七余以十五乘得三十个。二位相并，共得五十一个，满三十五去之，余一十六个。”2.32 大成算经之零约术关孝和的学生建部贤明在大成算经卷六中所讲的零约术如下乘数三个零八厘六毛六丝一忽四微二弱，问约率几何？答：乘率三百九十二，除率一百一十七。此题术文用图示表示为由上述图示可知，日本学者当时是用类似于中国的更相减损术来获得结果的。与世界有名的欧几里得算法在算理上是一致的。大成算经卷十二圆周率以=3.141592653589793238462463 二十五个有效数字为基准，用更相减损术求得十二个等率后来建部贤明的弟弟建部贤弘著不休缀术一书，把大成算经上述方法及其结果再次抄录，并说他们之所以用这种方法来计算渐进分数是厌烦其术，而且把载有这种方法的著作以祖冲之失传之书缀术命名，这就是说建部贤弘猜测祖冲之是用连分数法从小数近似值得出分数表达的。大成算经出版后，日本学者用更相减损术求渐进分数就比较普遍了。例如会田安明著算法零约术三卷就用这种方法求2，3，5的渐进分数。他从2=1.41421356出发，用更相减损术得到1.41421356=1+1 2.4 意大利斐波那契在算盘书中的描述意大利数学家斐波那契(Fabonacci，约1170-1250)在算盘书第十二章第八部分讲到第二类剩余问题。在空间、时间差距甚大的场景下，有与孙子算经中的“物不知数”几乎一致的内容。Let a contrived number be divided by 3,also by 5,also by 7;and ask each time what remains from each division.For each unity that remains from the division by 3,retain 70;for each unity that remains from the division by 5,retain 21;and for each unity that remains from the division by 7,retain 15.And as much as the number surpasses 105,subtract from it 105;and what remains to you is the contrived number.Example:suppose from the division by 3 the remainder is 2;for this you retain twice 70,or 140;from which you subtract 105, and 35 remains.From the division by 5,the remainder is 3;for which you retain three times 21,or 63,which you add to the above 35;you get 98;and from the vision by 7,the remainder is 4,for which you retain four times 15,or 60; which you add to the above 98,and you get 158;from which you subtract 105,and thee remainder is 53,which is the contrived number.以上过程即求一次同余式组问题：N r (mod3) r (mod5) r(mod7)N =70r +21r +15r -105n，选取适当的n，即可得到N的最小正整数解。 根据斐波那契的算法原则可知，求被3除余2，被5除余3，被7除余4的最小整数是这样“造”出来的。N=270?105=35，N=321=63，N=415=60所以此数为：35+63+60=158，158-105=53，所以此数为53。因此斐波那契给出的解为：N 105 n+53。其解释原理如下：70 1 (mod3 )0 (mod5 )0 (mod7)21 0 (mod3 )1( mod5 )0 (mod7)15 0 (mod3 )0 (mod5 )1( mod7)105 0 (mod3) 0 (mod5) 0 (mod7)因此，2 70 2 (mod3) 0 (mod5) 0 (mod7)3 21 0 (mod3) 3 (mod5) 0 (mod7)4 15 0 (mod3) 0 (mod5) 4 (mod7)把以上三式相加则得到，（2 70-105+3 21 +4 15）-105 =53 所以最小整数为53。通过斐波那契算法不难发现：算盘书中的算法与“物不知数”中的算法有一点差异,那就是在算盘书中将减去105的“做法”分布在每一步运算中。实际上上两种算法有着相同的本质。在造70,21,15这三个数的过程中，是欧几里得算法的一种体现。2.5德国数学家高斯对剩余定理的叙述1801年，大数学家高斯在算术研究中给出了一次同余式组的解法。1874年，德国数学家马蒂生(Ludwig Matthiessen，18301906)在给康托的一封信里证明：中国的大衍术与德国大数学家高斯的解法是等价的。指出其中的，和即为大衍术中的“用数”(Hulfszahlen)，在解，和过程中与欧几里得算法是一致的与中国解法也是一致的。华罗庚在从孙子的“神奇妙算”谈起中是这样解释的：如果用任何正整数a，b，c代表余数，那么，70是这样的一个数：除以3时有余数1，而除以5或7时没有余数。很明显，华罗庚先生依据的是高斯的解释。因此研究高斯关于剩余定理的叙述，意义重大，有助于比较中外数论思想发展的异同。2.5.1高斯对剩余定理的叙述算术研究第1章第36节译文如下：“当所有的模A，B，C，D，等等两两互素时，使用下列方法通常更为优越。确定一个数，相对于模A与1同余，相对于其它模的乘积与0同余。这就是说，由式子1/BCD等等(mod A)的一个值(最好是最小值)，用BCD等等所乘。类似地，令1(mod B)和0(mod ACD etc.)，1(mod C)和0(mod ABD etc.)，等等。于是，如果我们要寻找z，它与分别对应于模A，B，C，D等等的余数a，b，c，d等等同余，我们能够记作za+b+c+d etc.(mod ABCD etc)。解释原理如下aa(mod A)，并且其余的b，c，等等都0(mod A)，所以za(mod A)。za(mod A)b(mod B)c(mod C)d(mod D)。如果有1(mod A)0(mod B)0(mod C)0(mod D)，0(mod A)1(mod B)0(mod C)0(mod D)，0(mod A)0(mod B)1(mod C)0(mod D)，0(mod A)0(mod B)0(mod C)1(mod D)，则有za+b+c+d etc.(mod ABCD etc)。这样计算出的，保证满足“相对于模A与1同余，相对于其它模的乘积与0同余”。在处理两两互素模时，寻找一个常数1基础同余式组。它与原始同余式组，同余式个数相同，模相同，相对于某个模余数为常数1，相对于其它模余数为0。在计算a， 过程中是欧几里得算法的一种体现。26欧拉解法事实上，大数学家欧拉早在1734年的论文(Comm.Aead.Pet:op.，7，1734一5，46-66;CommArithColl，I，11一20)中就提出了关于一次同余式组的两个解法。我们重点讨论欧拉第处理两个同余式的解法，简称欧拉解法，其提法为:如果ab，求一个数Z，被a和b除所得的余数分别是P和q，即Z一ma+P一nb+q。采取求a，b最大公因数的方法，把a，b辗转相除，求出一系列余数:，d，。，直到某一个余数能整除v一P一q为止，括号中是一个级数，级数的最后一项取决于符合上述要求的余数。为简化叙述，这里只能采用两个数字例子来介绍欧拉的解法:数例一为利于比较中外算法，选用黄宗宪演算秦九韶“推计土功”题三 中国的欧几里得算法3.1 更相减损术3.11最大公约数最大公约数的概念起初来源于九章算术方田第五和第六题，九章算术是从先秦开始在长时期里经众多学者编纂修改，约于西汉中叶（公元前1世纪）最后成书。此题中求约分的方法称为更相减损法。原文第五题今有十八分之十二，问约之得几何答日三分之二原文第六题又 有九十一分之四十九，问约之得几何答日十三分之七约分 按约分者，物之数量，不可悉全，必以分言之，分之为数，繁则难用。设有四分之二者，繁而言之，亦可为八分之四；约而言之，则二分之一也。虽则异辞，至于为数，亦同归尔。法实难推，动有参差，故为术者先治诸分。术曰：可半者半之；不可半者，副置分母、子之数，以少减多，更相减损，求其等也。以等数约之。等数约之，即除也。七所以相减者，皆等数之重叠，故以等数约之。术日中 “可半者半之；不可半者，副置分母、子之数，以少减多，更相减损，求其等也。以等数约之。”这是九章算术对约分方法的完整总结。九章算术是以算筹为算具的数学书，现将上述算题作筹算图式，以帮助我们领会“更相减损术”术文的真实含义。一、上述演算过程表为现代形式为前面我们介绍过欧几里得算法，其实九章算术中求最大公约数的方法与具有世界声誉的欧几里德算法与我不谋而合，现比较两种算法在数理上的一致性。刘徽为约分术作了注解，注文最后说“等数约之，即除也，其所以相减者，皆等数之重叠，故以等数约之。”注文中“皆等数之重叠”是说分母，分子分母在辗转相除逐次所得余数变小。可见两种算法除了最后一步表述有区别外，全相一致。然而欧几里德只介绍了方法在他生活的年代以及绵延长达千年的希腊文化中却无人道出刘徽所说“其所以相减者，皆等数之重迭”这一重要理论依据。这种方法辗转流传直到1494年意大利帕西沃里（L.Paclioli,1445-1509）著数学大成还用以求最大公约数。明末李之藻与罗马传教士利玛窦合作编译同文算指书中介绍当时东西方流行的各种算术问题卷下称最大公约数为纽数梅文鼎看问题就比较客观,他虽也没有见过九章算术,在所著笔算约分中引述有关大意。说“古法曰,可半者半之,不可半者,以少减多,更相减损,求其有等,以等数约之以等数除母、子数,则皆除尽,西人谓之纽数。”3.2 祖冲之圆周率祖冲之是我国古代最有影响的数学家之一,莫斯科大学走廊里有其塑像。他对的研究真可谓“运筹于帷幌之中,决胜于干年之外”。遗憾的是,虽然祖率独步千年,但在这千余年中,外国人不知,中国人也知之甚少。隋书律历志中记载,祖冲之“所著之书名为缀术,学官莫能究其深奥,是故废而不理”。一部杰作就这样被埋没了。以现存的文献看,它的内容一定是相当精深的。隋书律历志载:古之九数，圆周率三，圆径率一，其术疏舛。自刘歆、张衡、刘徽、王蕃、皮延宗之徒各设新率，未臻折衷。宋末，南徐州从事史祖冲之，更开密法。以圆径一亿为一丈，圆周盈数三丈一尺四寸一分五厘九毫二秒七忽，朒数三丈一尺四寸一分五厘九毫二秒六忽，正数在盈朒二限之间。密率，圆径一百一十三，圆周三百五十五。约率，圆径七，周二十二。祖冲之推定圆周率的值在“盈”、“肭”二限之间，其中“盈”数为31415927，“肭”数31415926。即314159263.1415927约率22/7， 密率355/113 这一成果保持了900多年的领先记录，但史书并无记载祖冲之是用什么方法得到这一结果的。祖冲之又提出的圆周率的两个最佳渐进分数：约率227，密率355113。颇受人们重视和关注，祖冲之如何得到约密二率，在来源问题上有下列几种猜测。3.3“通其率”李继闵曾撰文认为大衍求一术来源于通其率算法，通其率的出处，在汉书律历志:“木，晨始见，去日半次。顺，日行十一分度二，百二十一日，始留，二十五日而旋。逆，日行七分度一，八十四日，复留，二十四日三分而旋。复顺，日行十一分度二，百一十一日有百八十二万八千三百六十二分而伏。凡见三百六十五日有百八十二万八千三百六十五分，除逆，定行星三十度百六十六万一千二百八十六分。凡见一岁，行一次而后伏，日行不盈十一分度一，伏三十三日三百三十三万四千七百三十七分，行星三度百六十七万三千四百五十三分。一见，三百九十八日五百一十六万三千一百二分，行星三十三度三百三十三万四千七百三十七分。通其率，故曰:日行千七百二十八分度之百四十五。”“土，晨始见，去日半次。顺，日行十五分度一，八十七日，始留，三十四日而旋。逆，日行八十一分度五，百一日，复留，三十三日八十六万二千四百五十五分而旋。复顺，日行十五分度一，八十五日而伏。凡见三百四十日八十六万二千四百五十五分，除逆，定行星五度四百四十七万三千九百三十分。伏，日行不盈十五分度三，百三十七日千七百一十七万一百七十分，行星七度八百七十三万六千五百七十分。一见，三百七十七日千八百三万二千百六十二五分，行星十二度千三百二十一万五百分。通其率，故曰:日行四千三百二十分度之百四十五。”“火，晨始见，去日半次。顺，日行九十二分度五十三，二百七十六日，始留，十日而旋。逆，日行六十二分度十七，六十二日，复留，十日而旋。复顺，日行九十二分度五十三，二百七十六日而伏。凡见六百三十四日，除逆，定行星三百一度。伏，日行不盈九十二分度七十三分，伏百四十六日千五百六十八万九千七百分，行星百一十四度八百二十一万八千五分。一见，七百八十日千五百六十八万九千七百分，凡行星四百一十五度八百二十一万千五分。通其率，故曰:日行万三千八百二十四分度之七千三百五十五。”大洐求一术秦九韶（12021261年）1247年写成著名的数术九章其最重要的数学成就“大洐总数术”（一次同余组解法）与“正负开方术”（高次方程数值解法），使这部宋代算经在中世纪世界数学史上占有突出的地位。但在秦代以前，这一方法早已部分地得到应用。在中国最早见于数学典籍的一次同余组问题是孙子算经中“物不知数问题。文本内容是：今有物不知其数，三三数之剩二，五五数之剩三，七七数之剩二，问物几何?答日：二十三术日：三三数之剩二，置一百四十；五五数之剩三，置六十三；七七数之剩二，置三十。并之得二百三十三。以二百一十减之，即得。凡三三数之剩一，则置七十，五五数之剩一，则置二十一，七七数之剩一，则置十五。一百六以上，以一百五减之，即得。“物不知数”问题解法中的140，,63,30都是心算出来的，70是5和7的公倍数,用3去除它余数是1。15是3和5的公倍数,用7去除它余数是1。21是3和7的公倍数,用5去除它余数是1。因此70是5和7的公倍数,用3去除它余数是2。21是3和7的公倍数,用5去除它余数是1,15是3和5的公倍数,用7去除它余数是1。未知的数用3除，所得第一个余数2，乘以70，是140；对于用5除所得的第二个余数是3，乘以21，得63；对于用7除所得的第三个余数2，乘以15，得30；再把所有的乘积加起来，即270+321+215=233。这个总和大于105，就从中减去105，233105=128。还是大于105，就再减去105，128一105=23，23是小于105的正整数，从而得出出这个未知数为23。 但是如果数据较大时，就很难轻而易举心算出来了，在孙子算经后的数百年没有见过有关的论述。直到公元十三世纪南宋数学家秦九韶在数术九章中提出大洐求一术，系统地论述了求一次同余式的一般方法。 秦九韶对一次同余式的一般解法包括三部分组成，第一部分为化非两两互素的问数（即模数）为两互素的定数的算法，第二部分是用辗转相除法求乘率的程序大洐求一术，这是求解一次同余式组的关键。第三部分是求乘率，定数等的一般公式。大洐求一术云：置奇右上，定居右下，立天元一千左上。先以右上除右下，所得商数，与左上一相生，入左下。然后乃以右行上下，以少除多，递互除之，所得商数，随即递互累乘，归左行上下，须使右上末后奇一而止，乃验左上所得，以为乘率。或奇数已见单一者，便为乘率。根据数文中的叙述，我们可以看出如何求出满足 zhong 的 ，乃是全部问题的关键，孙子