辗转相除，又名欧几里德算法(Euclidean algorithm)，乃求两个正整数之最大公约数的算法。它是已知最古老的算法, 其可追溯至公元前300年。

• 中文名称 辗转相除
• 外文名称 Euclidean algorithm
• 又名 欧几里德算法
• 简介 求两个正整数之最大公约数的算法

简介

　　它是已知最古老的算法, 其可追溯至公元前300年。它首次出现于欧几里德的《几何原本》(第VII卷，命题i和ii)中，而在中国则可以追溯至东汉出现的《九章算术》。它并不需要把二数作质因子分解。

算法内容

　　辗转相除法是利用以下性质来确定两个正整数 a 和 b 的最大公约数的:

　　1. 若 r 是 a ÷ b 的余数, 则

　　gcd(a,b) = gcd(b,r)

　　2. a 和其倍数之最大公约数为 a。

　　另一种写法是:

　　1. a ÷ b，令r为所得余数(0≤r<b)

　　若 r = 0，算法结束;b 即为答案。

　　2. 互换:置 a←b，b←r，并返回第一步。

算法证明

　　证明:

　　已知m=qn+p，即m整除n的商为q，余数为p(其中,m≥n,n>p)。

　　注意:使用(m,n)表示m和n的最大公约数;(n,p)表示n和p的最大公约数.用m|n表示m为n的因数。

　　对于任意的m和n的公因数r，都有r|m和r|n。根据等式m=qn+p，可知r|p(因为等式可写成ra=rbn+p)，则r为n和p的公因数。

　　因此，所有m和n的公因数，都是n与p的公因数。

　　同理可得，所有n与p的公因数，都是m与n的公因数。

　　因此，(m，n)=(n，p)，即m与n的最大公因数为n与m整除n后的余数q的最大公因数。

　　则对于任意两个整数a，b(其中a>=b)，其最大公因数为a整除b后的余数与b的最大公因数。

　　得证。

代码

　　计算机代码如下:

　　其中"a mod b"是指取 a ÷ b 的余数

　　。

　　例如，123456 和 7890 的最大公因子是 6, 这可由下列步骤看出:

　　a b a mod b

　　123456 7890 5106

　　7890 5106 2784

　　5106 2784 2322

　　2784 2322 462

　　2322 462 12

　　462 12 6

　　12 6 0

　　只要可计算余数都可用辗转相除法来求最大公约数。这包括多项式、复整数及所有欧几里德定义域(Euclidean domain)。

　　C程序:

　　辗转相除法的运算速度为 O(n)，其中 n 为输入数值的位数。