輾轉相除法

维基百科，自由的百科全书

Animation

輾轉相除法, 又名歐幾里得算法（Euclidean algorithm）乃求兩個正整數之最大公因數的算法。這是已知最古老的算法, 其可追溯至前300年。首次出現於歐幾里得的《幾何原本》（第VII卷，命题i和ii）中，而在中國則可以追溯至東漢出現的《九章算術》。這算法並不需要把二數作質因數分解。

[编辑] 古書記述

《九章算術·方田》作分數約簡時，提到求最大公因數方法：反覆把兩數的較大者減去較小者，直至兩數相等，這數就是最大公因數。這方法除了把除法換作減法外，與輾轉相除法完全相同。例如書中求91和49的最大公因數：

91 > 49, 91 - 49 = 42
49 > 42, 49 - 42 = 7
42 > 7, 42 - 7 = 35
35 > 7, 35 - 7 = 28
28 > 7, 28 - 7 = 21
21 > 7, 21 - 7 = 14
14 > 7, 14 - 7 = 7
7 = 7, 因此91和49的最大公因數是7

[编辑] 算法

輾轉相除法是利用以下性質來確定两个正整数 a 和 b 的最大公因數的：

若 r 是 a ÷ b 的餘數, 則

$gcd(a, b) = gcd(b, r)$
a 和其倍數之最大公因數為 a。

另一種寫法是：

a ÷ b，令r为所得餘数（0≤r＜b）

若 r = 0，算法结束；b 即为答案。
互换：置 a←b，b←r，并返回第一步。

[编辑] 證明

設
$\ a=bq+r$
欲證 $\ (a,b)=(b,r)$

先設

$\ (a,b)=d$
$\ (b,r)=e$

[编辑] 虛擬碼

這個算法可以用遞歸寫成如下:

function gcd(a, b) {
    if (a mod b)
        return gcd(b, a mod b);
    else
        return b;
}

或純使用迴圈:

function gcd(a, b) {
    define r as integer;
    while b ≠ 0 {
        r := a mod b;
        a := b;
        b := r;
    }
    return a;
}

其中「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）。

輾轉相除法的運算速度為 $O (n 2)$ ，其中 n 為輸入數值的位數。

[编辑] 參考資料

高德纳,《计算机程序设计艺术》, volume 1 and volume 2. Addison-Wesley.

[编辑] 外部链接