《欧几里得算法在历史上的不同呈现》由会员分享，可在线阅读，更多相关《欧几里得算法在历史上的不同呈现（26页珍藏版）》请在金锄头文库上搜索。
1、1欧几里得算法在历史上的不同呈现二 国外的欧几里得算法2.1 几何原本中的欧几里得算法2.11 欧几里得和他的几何原本欧几里得（Eudides 或 Eucleides，公元前三百年前后） ，是希腊数学家。欧几里得的几何原本是一部划时代的著作。中国传统数学的最大特点是以算为中心，没有形成如同古希腊数学那样的公理化体系。 几何原本开创了数学公理化的正确道路，促进了整个数学的发展。 几何原本全书共由十三卷组成，第一卷到第六卷为平面几何学，它是由徐光启，利玛窦在 1607 年共同译完，明末传入我国，补救我国数学研究中的不足。第七卷到第十卷为数论，但与中算不同的是，全用几何方式来叙述。其中第卷命题就是用
2、几何方式来叙述欧几里得算法。第十一卷到第十三卷为立体几何学。早在半个世纪以前，日本数学家小仓金之助把九章算术与几何原本进行比较，他认为九章算术是“中国的欧几里得” ，作为东西方数学的代表作， 九章算术与几何原本在数学发展史上的产生和流传有相似之处。欧几里得算法来源于几何原本 ，但欧几里得算法中算法思想却与古印度，日本，意大利，德国，以及我国古代现代许多数学研究一致。2.12 欧几里得算法几何原本第卷命题中原文如下“设有不相等的二数，若2依次从大数中不断地减去小数，若余数总是量不尽它前面的一个数，直到最后的余数为一个单位，则该二数互素” 。命题二中“已知两个不互素的数，求它们的最大公度数。 术文
3、如下 设 AB,CD 是不互素的两数，求 AB,CD 的最大公度数。如果 CD 量尽 AB ，那么它也能量尽它自己，那么 CD 就是 CD,AB 的最大公度数。且显然 CD 也是最大公度数，这是因为没有比 CD 大的数能量尽 CD ，但是，如果 CD 量不尽 AB，那么从 AB,CD 中的较大者中不断地减去较小者，如此，将有某个余数能量尽它前面的一个。这最后的余数不是一个单位，否则 AB,CD 就是互素的。 ”2.2 印度的不定方程组问题一次不定分析在中国，印度，古希腊数学中多有研究，特别是对印度数学家来说是非常重要的。他们非常重视一次不定分析的研究，曾一度用它来代表这门学科。342.3 日本
4、数学家关孝和的叙述据相关文献考证，日本数学发展是从钱明天皇时代开始的，历史5记载公元 554 年百济有历法博士到日本传授历法。602 年又有和尚关勒到日本传授天文知识。说明我国数学天文成果以朝鲜为跳板在公元六世纪已经传入日本。日本数学在发展中逐渐形成独特的体系，称为和算。日本被誉为和算之圣的数学家关孝和是数学家毛利的再传弟子。关孝和在解同余式问题中所拟题及其解法是深透的，特别是他的剩一术对秦九韶大衍求一术中划一程序的解释比黄宗宪要早一百多年。2.31 关孝和解同余式 19x=1(mod 27)关孝和用汉文写的括要算法卷二有剩一术，是用更想减损的方法计算同余式 ax=1(mod b)的解。原文如
5、下“今有以左一十九累加之得数，以右二十七累减之，剩一，问左总数几何？答：左总数190。 ”可以看出上文是解同余式 19x=1(mod 27)的问题。关孝和在解题术文中所说的解题程序如下“以左一十九，除右二十七，得商一，不尽（余数）八为甲。以甲不尽八，除左一十九，得商二，不尽三，为乙。以乙不尽三除甲，不尽八，得商二，不尽三，为丙。以丙不尽二除乙，不尽三，得商一，不尽一， 为丁，乃余一而止。”转换成图示为6紧接着还有四句术文如下“甲商与乙商相因，加定一，得三为子。子与丙商相因，加甲商，得七为丑。丑与丁商相因，加子，得一十。以左一十九乘之，得左总数一百九十，合问。 ”转换成数学语言为2.32 关孝和
6、解同余式组关孝和对解同余式组问题也作了深入研究。在括要算法卷二“剪管术”中自拟辅助题“今有物不知其数，只云五除余一个，七除余二个，问总数几何。 ”答数为十六个。这就是解同余式组关孝和作出术文“五余以二十一乘得二十一个，七余以十五乘得三十个。二位相并，共得五十一个，满三十五去之，余一十六个。”72.32 大成算经之零约术关孝和的学生建部贤明在大成算经卷六中所讲的零约术如下乘数三个零八厘六毛六丝一忽四微二弱，问约率几何？答：乘率三百九十二，除率一百一十七。此题术文用图示表示为由上述图示可知，日本学者当时是用类似于中国的更相减损术来获得结果的。与世界有名的欧几里得算法在算理上是一致的。大成算经卷十二
7、圆周率以 =3.141592653589793238462463 8二十五个有效数字为基准，用更相减损术求得十二个等率后来建部贤明的弟弟建部贤弘著不休缀术一书，把大成算经上述方法及其结果再次抄录，并说他们之所以用这种方法来计算渐进分数是厌烦其术，而且把载有这种方法的著作以祖冲之失传之书缀术命名，这就是说建部贤弘猜测祖冲之是用连分数法从小数近似值得出分数表达的。大成算经出版后，日本学者用更相减损术求渐进分数就比较普遍了。例如会田安明著算法零约术三卷就用这种方法求2，3，5的渐进分数。他从2=1.41421356 出发，用更相减损术得到 1.41421356=1+1 2.4 意大利斐波那契在算盘书
8、中的描述意大利数学家斐波那契(Fabonacci，约 1170-1250)在算盘书第十二章第八部分讲到第二类剩余问题。在空间、时间差距甚大的场景下，有与孙子算经中的“物不知数”几乎一致的内容。9Let 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
9、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
10、 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;fro
11、m 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 的最小整数是这样“造”出来的。10N=270?105=35，N=321=63，N=415=60所以此数为：35+63+60=158，158-105=53，所以此数为 53。因此斐波
12、那契给出的解为：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。通过斐波那契算法
13、不难发现：算盘书中的算法与“物不知数”中的算法有一点差异,那就是在算盘书中将减去 105 的“做法”分布在每一步运算中。实际上上两种算法有着相同的本质。在造70,21,15 这三个数的过程中，是欧几里得算法的一种体现。2.5 德国数学家高斯对剩余定理的叙述1801 年，大数学家高斯在算术研究中给出了一次同余式组的解法。1874 年，德国数学家马蒂生(Ludwig 11Matthiessen，18301906)在给康托的一封信里证明：中国的大衍术与德国大数学家高斯的解法是等价的。指出其中的 ， 和 即为大衍术中的“用数”(Hulfszahlen)，在解 ， 和 过程中与欧几里得算法是一致的与中国
14、解法也是一致的。华罗庚在从孙子的“神奇妙算”谈起中是这样解释的：如果用任何正整数a，b，c 代表余数，那么，70 是这样的一个数：除以 3 时有余数1，而除以 5 或 7 时没有余数。很明显，华罗庚先生依据的是高斯的解释。因此研究高斯关于剩余定理的叙述，意义重大，有助于比较中外数论思想发展的异同。2.5.1 高斯对剩余定理的叙述算术研究第 1 章第 36 节译文如下：“当所有的模 A，B，C，D，等等两两互素时，使用下列方法通常更为优越。确定一个数 ，相对于模 A 与 1 同余，相对于其它模的乘积与 0 同余。这就是说， 由式子 1/BCD 等等(mod A)的一个值(最好是最小值)，用 BC
15、D 等等所乘。类似地，令 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，等等都120(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(m
16、od 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;CommArith
