輾轉相除法（最大公因數）計算機

輸入計算

第一個數 (a)

第二個數 (b)

結果

最大公因數

12

gcd(48, 36)

最大公因數（GCD）	12
最小公倍數（LCM）	144

什麼是輾轉相除法？

輾轉相除法（又稱歐幾里得演算法）是目前已知最古老的演算法之一，由古希臘數學家歐幾里得約在西元前 300 年提出。它能有效率地求出兩個整數的最大公因數（GCD），也就是能同時整除這兩數、且不留餘數的最大整數。本計算機還會一併算出最小公倍數（LCM），這個結果可直接由 GCD 推導而來。

如何使用本計算機

在上方欄位輸入兩個整數後送出即可。計算機會取輸入值的絕對值，反覆套用 \(\gcd(a, b) = \gcd(b, a \bmod b)\) 這條規則，直到餘數變成零為止，最後同時回報 GCD 與 LCM。

公式解析

核心觀念在於：把較大的數換成它除以較小數後的餘數，兩數的最大公因數並不會改變。以符號表示即

$$\gcd(a, b) = \gcd(b, a \bmod b)$$

如此反覆運算，直到 \(b = 0\)；此時最後一個非零的數值就是 GCD。接著再用

$$\operatorname{lcm}(a, b) = \frac{a \times b}{\gcd(a, b)}$$

求出最小公倍數，因為兩數的乘積等於其 GCD 與 LCM 的乘積。

Advertisement

歐幾里得演算法將 \((a, b)\) 替換為 \((b, a \bmod b)\)，直到餘數為零。

實例演練

求 \(\gcd(48, 36)\)：\(48 \bmod 36 = 12\)，所以轉為 \(\gcd(36, 12)\)。接著 \(36 \bmod 12 = 0\)，因此 GCD 為 12。最小公倍數則是 $$\frac{48 \times 36}{12} = \frac{1728}{12} = 144$$

從幾何上看，最大公因數是能恰好鋪滿 \(a \times b\) 矩形的最大正方形的邊長。

常見問題

如果其中一個數是零怎麼辦？ \(\gcd(a, 0) = a\)。演算法會自然處理這種情況——迴圈會立即停止，並回傳那個非零的數值。

a 與 b 的順序會有影響嗎？ 不會。\(\gcd(a, b) = \gcd(b, a)\)；演算法在第一步就會自動修正順序。

可以輸入負數嗎？ 可以。計算機會取絕對值，因為依慣例最大公因數定義為正數。