什麼是歐幾里得算法

歐幾里得算法 （Euclidean algorithm），又稱輾轉相除法，是一種用於高效計算兩個自然數（或整數）最大公因數（Greatest Common Divisor, GCD）的算法。大約在公元前300年，古希臘數學家歐幾里得在其數學著作《幾何原本》（Elements）第7卷中記載了該算法，它也被廣泛認為是「人類最古老的算法」之一。

求最大公因數最樸素的方法是將兩個數分別進行質因數分解，然後將相同的質因數相乘。但是，當數字變得非常龐大時，質因數分解本身的計算量會變得極其巨大，難以在現實時間內得出結果。相反，如果使用 歐幾里得算法 ，即使是長達數千位的巨大數字，也能以極快的速度計算出它們的最大公因數。

基本定理與原理

設兩個自然數 $a$ 和 $b$ （$a \ge b$）的最大公因數為 $\gcd(a, b)$。歐幾里得算法基於以下簡單的定理：

$$ a = bq + r \implies \gcd(a, b) = \gcd(b, r) $$

也就是說，它利用了這樣一個性質：「當 $a$ 除以 $b$ 的商數為 $q$ 、餘數為 $r$ 時， $a$ 和 $b$ 的最大公因數等於 $b$ 和 $r$ 的最大公因數。」

定理的證明

為什麼 $\gcd(a, b) = \gcd(b, r)$ 成立呢？讓我們簡單證明一下。

設 $d$ 為 $a$ 和 $b$ 的任意公因數。此時，可以表示為 $a = md, b = nd$ （$m, n$ 為整數）。
由 $a = bq + r$ 可得， $r = a - bq$。
將前面的式子代入，得到 $r = md - (nd)q = d(m - nq)$。
因為 $m - nq$ 是整數，所以 $d$ 也是 $r$ 的因數。因此， $a$ 和 $b$ 的公因數 $d$ 也是 $b$ 和 $r$ 的公因數。
反之，設 $e$ 為 $b$ 和 $r$ 的公因數，可以表示為 $b = k e, r = l e$。
$a = bq + r = (k e)q + l e = e(kq + l)$，因此 $e$ 是 $a$ 的因數。所以， $b$ 和 $r$ 的公因數 $e$ 也是 $a$ 和 $b$ 的公因數。
因此， $\{a, b\}$ 的公因數集合與 $\{b, r\}$ 的公因數集合完全一致，它們的最大值（即最大公因數）也相等。 $\blacksquare$

算法流程圖

利用這一性質，歐幾里得算法通過不斷重複除法運算，直到餘數為 $0$ 為止。

  flowchart TD
    Start["開始: 輸入 a, b"] --> Check{"b == 0 ?"}
    Check -- "Yes" --> End["GCD 為 a"]
    Check -- "No" --> Calc["r = a % b"]
    Calc --> Update["a = b, b = r"]
    Update --> Check

具體計算範例

作為範例，讓我們求出 $a = 1071$ 和 $b = 1029$ 的最大公因數。

$1071 \div 1029 = 1 \cdots 42$ （更新為 $a=1029, b=42$）
$1029 \div 42 = 24 \cdots 21$ （更新為 $a=42, b=21$）
$42 \div 21 = 2 \cdots 0$ （餘數為 $0$ ，結束計算）

最後作為除數留下的 $21$ ，就是 $1071$ 和 $1029$ 的最大公因數。

程式實作

Python實作

在Python中，可以使用遞迴函數或者 while 迴圈來實作。由於迴圈方法沒有函數呼叫的額外開銷，因此執行速度更快。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
def gcd_loop(a: int, b: int) -> int:
    """
    使用迴圈實作歐幾里得算法
    """
    while b != 0:
        a, b = b, a % b
    return a

def gcd_recursive(a: int, b: int) -> int:
    """
    使用遞迴實作歐幾里得算法
    """
    if b == 0:
        return a
    return gcd_recursive(b, a % b)

print(gcd_loop(1071, 1029))  # 輸出: 21

C++實作

在C++17及更高版本中， <numeric> 標頭檔標準實作了 std::gcd ，但如果要自己編寫程式碼，可以參考以下方式：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
#include <iostream>

// 計算最大公因數的函數（遞迴版）
int gcd(int a, int b) {
    if (b == 0) {
        return a;
    }
    return gcd(b, a % b);
}

int main() {
    std::cout << "GCD: " << gcd(1071, 1029) << std::endl; // 輸出: 21
    return 0;
}

時間複雜度與拉梅定理

歐幾里得算法到底有多快呢？關於其計算複雜度，法國數學家加布里埃爾·拉梅在1844年證明的 拉梅定理 （Lamé’s theorem）非常著名。

拉梅定理 對兩個自然數 $a, b$ （$a > b$）應用歐幾里得算法時，除法的次數不超過 $b$ 在十進位下位數的 $5$ 倍。

由此可知，該算法的時間複雜度為 $O(\log(\min(a, b)))$。

最壞的情況（即除法次數最多的情況）發生在輸入費氏數列的相鄰兩項時。例如，在求 $F_{n+2}$ 和 $F_{n+1}$ 的最大公因數的過程中，商數始終為 $1$，並不斷向更小的費氏數過渡。

擴展歐幾里得算法

不僅能求出最大公因數，還能求出滿足以下裴蜀定理（Bézout’s identity）的整數 $x, y$ 的算法，被稱為 擴展歐幾里得算法 （Extended Euclidean algorithm）。

$$ ax + by = \gcd(a, b) $$

擴展歐幾里得算法的實作

在遞迴呼叫返回的過程中，逆向推導出 $x, y$ 的係數。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
def ext_gcd(a: int, b: int) -> tuple[int, int, int]:
    """
    返回滿足 ax + by = gcd(a, b) 的 (gcd, x, y) 的函數
    """
    if b == 0:
        return a, 1, 0
    
    g, x1, y1 = ext_gcd(b, a % b)
    x = y1
    y = x1 - (a // b) * y1
    
    return g, x, y

g, x, y = ext_gcd(111, 30)
print(f"gcd: {g}, x: {x}, y: {y}")
# 輸出: gcd: 3, x: 3, y: -11
# 驗證: 111 * 3 + 30 * (-11) = 333 - 330 = 3

在現代社會中的應用（RSA加密等）

擴展歐幾里得算法不僅僅是一個數學難題，它還是支撐現代網際網路社會不可或缺的技術。一個典型的例子就是 RSA加密 。在RSA加密的金鑰生成過程中，對於某個數 $e$ 和歐拉函數 $\phi(N)$ ，需要求解滿足 $e d \equiv 1 \pmod{\phi(N)}$ 的私鑰 $d$ （模反元素）。因為它可以轉化為 $ed + k\phi(N) = 1$ 的形式，所以我們可以直接使用擴展歐幾里得算法以極快的速度計算出 $d$。