2.2 最大公因數與擴展歐幾里得#

概念說明#

兩個整數的最大公因數（greatest common divisor, gcd）是同時整除它們的最大正整數。求 gcd 的歐幾里得演算法出自《幾何原本》（約西元前 300 年），是現存最古老的演算法之一，核心是一條簡單的恆等式：

gcd(a, b) = gcd(b, a mod b)，且 gcd(a, 0) = a

因為「整除 a、b 的數」與「整除 b、a mod b 的數」是同一批。每做一次取模，第二個參數至少減半，所以迭代次數是對數級——極端高效。

擴展歐幾里得演算法（extended Euclidean algorithm）更進一步：在求出 g = gcd(a, b) 的同時，找出整數 x, y 滿足貝祖等式 ax + by = g。這看似只是附加資訊，實則威力強大：它讓我們能解線性同餘方程 ax ≡ b (mod m)、求 a 在模 m 下的反元素（即 ax ≡ 1 (mod m) 的解），而模反元素正是 RSA 解密、中國剩餘定理（3.1 節）的必要零件。

演算法步驟#

基本歐幾里得（遞迴）： 1. 若 b = 0，回傳 a。 2. 否則回傳 gcd(b, a mod b)。

擴展歐幾里得（遞迴）： 1. 若 b = 0，回傳 (a, 1, 0)（因為 a·1 + 0·0 = a）。 2. 遞迴求出 g = gcd(b, a mod b) 與其係數 (x₁, y₁)，使得 b·x₁ + (a mod b)·y₁ = g。 3. 因為 a mod b = a − ⌊a/b⌋·b，代入整理得： g = b·x₁ + (a − ⌊a/b⌋·b)·y₁ = a·y₁ + b·(x₁ − ⌊a/b⌋·y₁) 所以回傳 (g, y₁, x₁ − ⌊a/b⌋·y₁)。

Python 程式碼範例#

def gcd(a, b):
    """歐幾里得演算法（迭代版）"""
    while b:
        a, b = b, a % b
    return abs(a)

def ext_gcd(a, b):
    """回傳 (g, x, y) 使得 a*x + b*y = g = gcd(a, b)"""
    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)

def mod_inverse(a, m):
    """求 a 在模 m 下的反元素；不存在則回傳 None"""
    g, x, _ = ext_gcd(a % m, m)
    if g != 1:
        return None
    return x % m

# 基本測試
print(gcd(48, 18))          # 6
print(gcd(2**100, 2**60))   # 1152921504606846976（大數沒問題）

# 貝祖等式驗證
g, x, y = ext_gcd(240, 46)
print(f"240*({x}) + 46*({y}) = {240*x + 46*y}")   # = 2 = gcd(240,46)

# 模反元素：3 在模 11 下的反元素是 4（因為 3*4 = 12 ≡ 1 mod 11）
inv = mod_inverse(3, 11)
print(inv, (3 * inv) % 11)  # 4 1

# 應用：解同餘方程 7x ≡ 3 (mod 26)
g, x, _ = ext_gcd(7, 26)    # gcd = 1，方程有解
print((x * 3) % 26)         # 11，因為 7*11 = 77 ≡ 3 (mod 26)

# 與標準庫比對
import math
print(gcd(123456789, 987654321) == math.gcd(123456789, 987654321))

複雜度分析#

歐幾里得演算法最壞情況發生在相鄰的費波那契數（如 gcd(F_{k+1}, F_k)）：此時迭代次數約為 O(log min(a, b))，由拉梅定理可知迭代次數不超過較小數十進位位數的 5 倍。擴展版每步多做一次乘法與減法，漸近複雜度相同。模反元素存在若且唯若 gcd(a, m) = 1，這個判斷在 mod_inverse 中已自動完成——這也是為什麼 RSA 要求加密指數與 φ(n) 互質。順帶一提，Python 3.8+ 的 pow(a, -1, m) 也內建了模反元素計算，可用來驗證自己的實作。

練習#

修改 ext_gcd 為迭代版本（不用遞迴），處理 a、b 都很大（各 100 位）的情況，確認不會觸發遞迴深度限制。
寫一個函式 solve_congruence(a, b, m)，回傳 ax ≡ b (mod m) 的所有解（模 m/gcd(a,m) 意義下），並用 12x ≡ 20 (mod 28) 測試。
用窮舉驗證：對所有 1 ≤ a < 26 且 gcd(a, 26) = 1 的 a，mod_inverse(a, 26) 都滿足 (a·inv) % 26 == 1，並列出這些 a（它們正是仿射密碼可用的密鑰）。