算法：最大公约数（GCD）

1. 最大公约数？

因数、倍数：设 a, b 是整数，b !=0。如果有一个整数 c，它使得 a = bc，则 a 叫做 b 的倍数，b 叫做 a 的因数。我们有时说，b 能整除 a 或 a 能被 b 整除，表示为 b|a。

公因数、最大公因数：如果 n >=2 是整数，而 a1, a2, ..., an 和 d 都是正整数。又设 d|a1，d|a2，d|a3，...，d|an，则 d 叫做 a1，a2，...，an 的公因数。公因数中的最大的那一个数叫做 a1，a2，a3，...，an 的最大公因数，表示为 (a1, a2, ..., an) = d。

2. 辗转相除法？

辗转相除法， 又名欧几里德算法（Euclidean algorithm），是求最大公约数的一种方法。方法是：用较大数除以较小数，再用出现的余数（第一余数）去除除数，再用出现的余数（第二余数）去除第一余数，如此反复，直到最后余数是0为止。那么最后的除数就是这两个数的最大公约数。

例：求 123456 和 7890 的最大公因数。

图：辗转相除过程

答： 123456 和 7890 的最大公因数是 6.

3. 数学解释？

辗转相除法的关键是

一个数学事实

GCD(a, b) = GCD(b, a mod b)

图：辗转相除数学证明

4. 程序代码？

图：辗转相除算法