投稿
  1. 小新网首页
  2. 创业项目

中国欧几里得（欧几里得算法求最大公约数）

zhanzhan • • 创业项目

中国欧几里得（欧几里得算法求最大公约数）

欧几里得，有时被称为亚历山大里亚的欧几里得，以便区别于墨伽拉的欧几里得，希腊化时代的数学家，被称为“几何学之父”。他活跃于托勒密一世时期的亚历山大里亚，也是亚历山太学派的成员。他在著作《几何原本》中提出五大公设，成为欧洲数学的基础。欧几里得也写过一些关于透视、圆锥曲线、球面几何学及数论的作品。欧几里得几何被广泛的认为是数学领域的经典之作。

中国欧几里得（欧几里得算法求最大公约数）

节选自维基百科, [遇见数学] 有修改, 转载请注明.

生平资料

欧几里得（Euclid）是希腊文Ε?κλε?δη? 的英化名字，意思是“好的名誉”。欧几里得生前活跃于亚历山大图书馆，而且很有可能曾在柏拉图学院学习。直到现在都无法得知欧几里得的生卒日期、地点和细节。直到现在，还没有找到任何欧几里得在世时期所画的画像，所以现存的欧几里得画像都是出于画家的想象。

欧几里得的生平资料流传到现在的很少，而大部分关于欧几里得的资料都是来自公元450年时普罗克洛的评论，及公元320年帕普斯的评论，距欧几里得有几个世纪之久。

中国欧几里得（欧几里得算法求最大公约数）

位于牛津大学自然历史博物馆的欧几里得石像(图自维基)

普罗克洛在他的《对几何原本的评论》（Commentary on the Elements）中简单的介绍了欧几里得。根据普罗克洛的说法，欧几里得属于柏拉图那一派，将《几何原本》集合在一起，这些著作原来是由柏拉图的学生（特别是欧多克索斯、泰阿泰德及欧普斯的腓力等）所写的，普罗克洛认为欧几里得没有比他们年轻多少，不过因为阿基米德（公元前287-212年）有提到欧几里得，他应该有活到托勒密一世的年代。阿基米德文章中有一些明显引用欧几里得著作的段落，虽然后来发现是后人加入的，一般仍认为欧几里得写作的年代比阿基米德要早。

几何原本

《几何原本》（古希腊语：Στοιχε?α，Stoicheia）是古希腊数学家欧几里得所著的一部数学著作，共13卷。这本著作是现代数学的基础，据估计在西方是仅次于《圣经》的出版版本最多的书籍。在四库全书中归赖于子部天文算法算书类。

《几何原本》虽然其中的许多内容是来自早期的数学家，但欧几里得的贡献是将这些资料整理成单一的，有逻辑架构的作品，容易使用也容易参考，其中有严谨的数学证明系统，是后来2300年数学的基础。

中国欧几里得（欧几里得算法求最大公约数）

俄克喜林库斯29号莎草纸，现存最早的几何原本残页之一，在俄克喜林库斯发现的，其年代约为西元后100年。插图和第2卷的命题5相同

几何原本对于几何学、数学和科学的未来发展，对于西方人的整个思维方法都有极大的影响。《几何原本》的主要对象是几何学，但它还处理了数论、无理数理论等其他课题，例如著名的欧几里得引理和求最大公因数的欧几里得算法。几何原本也说明完全数和梅森质数的关系（欧几里得-欧拉定理）、质数有无限多个（欧几里得定理）、有关因式分解的欧几里得引理（导出了算术基本定理及整数分解的唯一性）等。

欧几里得使用了公理化的方法。公理（Axioms）就是确定的、不需证明的基本命题，一切定理都由此演绎而出。在这种演绎推理中，每个证明必须以公理为前提，或者以被证明了的定理为前提。这一方法后来成了建立任何知识体系的典范，在差不多二千年间，被奉为必须遵守的严密思维的范例。《几何原本》是古希腊数学发展的顶峰。欧几里得将公元前七世纪以来希腊几何积累起来的丰富成果，整理在严密的逻辑系统运算之中，使几何学成为一门独立的、演绎的科学。

欧几里得在《几何原本》中提到的几何系统后来简称为几何，长久以来视为唯一一种可能的几何方式，不过当数学家在19世纪发现非欧几里得几何后，上述的几何就称为欧几里得几何。

中国最早的《几何原本》译本是1607年意大利传教士利玛窦和中国学者徐光启根据德国神父克里斯托弗·克拉维乌斯校订增补的拉丁文本《欧几里得原本》（15卷）合译的，定名为《几何原本》，几何的中文名称就是由此而得来的。他们只翻译了前6卷，后9卷由英国人伟烈亚力和中国科学家李善兰在1857年译出。

欧几里得算法

在数学中，辗转相除法，又称欧几里得算法（英语：Euclidean algorithm），是求最大公约数的算法。辗转相除法首次出现于欧几里得的《几何原本》（第VII卷，命题i和ii）中，而在中国则可以追溯至东汉出现的《九章算术》。

两个整数的最大公约数是能够同时整除它们的最大的正整数。辗转相除法基于如下原理：两个整数的最大公约数等于其中较小的数和两数的差的最大公约数。例如，252和105的最大公约数是21（252=21×12; 105=21×5）；因为 252 ? 105 = 21 × (12 ? 5) = 147 ，所以147和105的最大公约数也是21。在这个过程中，较大的数缩小了，所以继续进行同样的计算可以不断缩小这两个数直至其中一个变成零。这时，所剩下的还没有变成零的数就是两数的最大公约数。由辗转相除法也可以推出，两数的最大公约数可以用两数的整数倍相加来表示，如21 = 5 × 105 + (?2) × 252 。这个重要的结论叫做裴蜀定理。

 

 

两条线段长分别可表示252和105，则其中每一小分段长代表最大公约数21。如动画所示，只要辗转地从大数中减去小数，直到其中一段的长度为0，此时剩下的一条线段的长度就是252和105的最大公因数。

辗转相除法有很多应用，它甚至可以用来生成全世界不同文化中的传统音乐节奏。在现代密码学方面，它是RSA算法（一种在电子商务中广泛使用的公钥加密算法）的重要部分。它还被用来解丢番图方程，比如寻找满足中国剩余定理的数，或者求有限域中元素的逆。辗转相除法还可以用来构造连分数，在施图姆定理和一些整数分解算法中也有应用。辗转相除法是现代数论中的基本工具。

辗转相除法处理大数时非常高效，如果用除法而不是减法实现，它需要的步骤不会超过较小数的位数（十进制下）的五倍。拉梅于1844年证明了这点，同时这也标志着计算复杂性理论的开端。

本文来自作者:zhanzhan，不代表小新网立场！

转载请注明：https://www.xiaoxinys.cn/145069.html

赞 (0)
zhanzhanzhanzhan注册用户
0
上一篇 2022-09-02 10:13:00
下一篇 2022-09-02 10:18:00

相关推荐

版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌抄袭侵权/违法违规的内容， 请联系我们举报，一经查实，本站将立刻删除。