辗转相除法 - 基础数学 我爱数学网-数学爱好者的家园-中国专业化的数学论坛之一

我爱数学网-数学爱好者的家园-中国专业化的数学论坛之一

查看: 476|回复: 1

[数学综合] 辗转相除法

[复制链接]

120

主题

174

帖子

575

积分

小学四年级

Rank: 3

积分
575

最佳新人

发表于 2014-10-24 11:05:13 | 显示全部楼层 |阅读模式
本帖最后由 zjsgtc 于 2014-10-24 11:22 编辑

辗转相除法, 又名欧几里德算法(Euclidean algorithm)乃求两个正整数之最大公因子的算法。它是已知最古老的算法, 其可追溯至3000年前。
在数学中,辗转相除法,又称欧几里得算法,是求最大公约数的算法。辗转相除法首次出现于欧几里得的《几何原本》(第VII卷,命题yⅠ和Ⅱ)中,而在中国则可以追溯至东汉出现的《九章算术》。
两个整数的最大公约数是能够同时整除它们的最大的正整数。辗转相除法基于如下原理:两个整数的最大公约数等于其中较小的数和两数的相除余数的最大公约数。例如,252和105的最大公约数是21(252 = 21 × 12;105 = 21 × 5);因为252 / 105 = 2余42,所以105和42的最大公约数也是21。在这个过程中,较大的数缩小了,所以继续进行同样的计算可以不断缩小这两个数直至余数变为零。这时的除数就是所求的两个数的最大公约数。由辗转相除法也可以推出,两数的最大公约数可以用两数的整数倍相加来表示,如21 = 5 × 105 + (−2) × 252。这个重要的等式叫做贝祖等式。
辗转相除法最早出现在欧几里得的几何原本中(大约公元前300年),所以它是现在仍在使用的算法中最早出现的。这个算法原先只用来处理自然数,但在19世纪,辗转相除法被推广至其他类型的数,如高斯整数和一元多项式。自此,现代抽象代数概念如欧几里得整环开始出现。后来,辗转相除法又扩展至其他数学领域,如纽结理论和多元多项式。
辗转相除法有很多应用,它甚至可以用来生成全世界不同文化中的传统音乐节奏。在现代密码学方面,它是RSA算法(一种在电子商务中广泛使用的公钥加密算法)的重要部分。它还被用来解丢番图方程,寻找满足中国剩余定理的数,或者求有限域的倒数。辗转相除法还可以用来构造连分数,在施图姆定理和一些整数分解算法中也有应用。辗转相除法是现代数论中的基本工具。
辗转相除法处理大数时非常高效,它需要的步骤不会超过较小数的位数(十进制下)的五倍。加百利·拉梅(Gabriel Lamé)于1844年证明了这点,开创了计算复杂性理论。











回复

使用道具 举报

50

主题

1955

帖子

3568

积分

高中二年级

Rank: 5Rank: 5Rank: 5

积分
3568

活跃会员灌水之王最佳新人

发表于 2015-3-9 17:50:12 | 显示全部楼层
长知识了
回复

使用道具 举报

您需要登录后才可以回帖 登录 | 会员注册

本版积分规则

Powered by Discuz! X3.2

© 2001-2013 Comsenz Inc

关于我们 | 网站地图 | 我爱数学网 ( 沪ICP备16005585号-3  

GMT+8, 2019-11-21 03:24 征信网

快速回复 返回顶部 返回列表