辗转相除法(数学算法) : 一般指本词条
欧几里德算法
数学算法
欧几里德算法又称辗转相除法，是指用于计算两个非负整数a，b的最大公约数。应用领域有数学和计算机两个方面。计算公式gcd(a,b) = gcd(b,a mod b)。
1/2
欧几里德算法和扩展欧几里德算法可使用多种编程语言实现。
基本信息
- 中文名
欧几里德算法
- 外文名
Euclidean Algorithm 或者 Euclid's algorithm
- 原理
gcd(a,b) = gcd(b,a mod b)
- 应用
计算两个正整数a、b的最大公约数
- 领域
数学1、计算机
- 别名
辗转相除法
- 所属学科
数学
基本简介
1/3
欧几里德算法是用来求两个正整数最大公约数的算法。是由古希腊数学家欧几里德在其著作《The Elements》中最早描述了这种算法,所以被命名为欧几里德算法。
扩展欧几里德算法可用于RSA加密等领域。
假如需要求 1997 和 615 两个正整数的最大公约数,用欧几里德算法，是这样进行的：
至此，最大公约数为1
以除数和余数反复做除法运算，当余数为 0 时，取当前算式除数为最大公约数，所以就得出了 1997 和 615 的最大公约数 1。
计算证明
1/3
其计算原理依赖于下面的定理：
定理：两个整数的最大公约数等于其中较小的那个数和两数相除余数的最大公约数。最大公约数（Greatest Common Divisor）缩写为GCD。
gcd(a,b) = gcd(b,a mod b) (不妨设a>b 且r=a mod b ,r不为0)