辗转向除法的实质

在几乎大多数程序设计语言中，都讲过一个求两个整数的最大公约数的方法，叫做辗转相除法。很多人都会写这个程序，却不了解为什么。我给解释一下。

辗转相除法，是由欧几里德算法而来。其基本原理如下：

如果要求两个正整数a和b（假设a>b，其实这并不影响求解算法）的最大公约数，可以表示成下面的式子：

a=b×q+r （1）

其中，q表示a除以b所得的商，r表示余数。

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

因为在（1）式中，可以看出，如果一个数能够同时整除a和b，则必能同时整除b和r；而能够同时整除b和r的数也必能同时整除a和b。即a和b的公约数与b和r的公约数是相同的，其最大公约数也是相同的。

辗转相除法, 又名欧几里德算法（Euclidean algorithm）乃求两个正整数之最大公因子的算法。它是已知最古老的算法, 其可追溯至前300年。它首次出现于欧几里德的《几何原本》（第VII卷，命题i和ii）中，而在中国则可以追溯至东汉出现的《九章算术》。它并不需要把二数作质因子分解。

证明：
设两数为a、b(b＜a)，求它们最大公约数(a、b)的步骤如下：用b除a，得a＝bq?1＋r?1（0≤r?1＜b）。若r?1=0，则 (a，b)＝b；若r?1≠0，则再用r?1除b，得b＝r?1q?2＋r?2（0≤r?2＜r?1）。若r?2＝0，则(a，b)＝r?1，若 r?2≠0，则继续用r?2除r?1，……如此下去，直到能整除为止。其最后一个非零余数即为(a，b)。

[编辑] 算法

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

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

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

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

另一种写法是：

1. a ÷ b，令r为所