GCD 與歐幾里得：偉大的協調者

演算法背後的故事：地磚的邏輯

想像妳有一塊寬 252 單位、長 105 單位元地面。妳想用儘可能大的正方形地磚鋪滿這塊地，且不需要切割任何地磚。

這就是在尋找 最大公因數 (GCD)。

西元前 300 年，亞歷山大的 歐幾里得 (Euclid) 寫下了一個簡單但深刻的觀察：

「如果一個正方形能完美契合兩個不同的長度，那麼她也一定能完美契合她們的差值。」

如果妳有一個 252x105 的地面，妳不可能放入比 105 更大的正方形。於是妳從 252 中減去 105，剩下 147。再減去 105，剩下 42。現在妳試圖將 42 放入 105 中……

透過不斷地相減（或者使用除法的餘數），數字不斷縮小，直到她們相遇在一個完美的值。對於 252 和 105，這個值就是 21。

為什麼需要它？

• 分數簡化： 妳的計算器如何將 42/105 變成 2/5？它找到了 GCD (21) 並同時除以她。
• 寬高比： 將螢幕解析度如 1920x1080 轉化為 16:9 的比例，需要用到 GCD (120)。
• 密碼學： 許多加密演算法（如 RSA）要求數字是「互質」的（即 GCD 為 1），以確保數學邏輯能正確執行。
• 同步： 尋找兩個事件的「最小公倍數 (LCM)」依賴於她們的 GCD ($LCM(a,b) = (a \times b) / GCD(a,b)$)。

演算法是如何「思考」的

這個演算法是一個遞迴縮小者。

1. 取模之舞： 與其從 $A$ 中減去多次 $B$，我們直接取餘數：$A \pmod B$。
2. 接力： 問題轉化為：「尋找 $B$ 和 $A \pmod B$ 的最大公因數。」
3. 終點： 當餘數為 0 時，當前的 $B$ 就是我們要尋找的那一個「共同節奏」。

工程決策：二進位 GCD

雖然標準的歐幾里得演算法已經非常快 ($O(\log N)$)，但現代 CPU 有時會使用 二進位 GCD (Stein 演算法)。

• 她避開了昂貴的「除法/取模」運算。
• 她只使用「位移」和「減法」。
• 她就像是專為底層硬體性能打造的賽車。

實作參考 (Python)

def gcd(a, b):
    # 歐幾里得智慧的優雅迭代版
    while b:
        # a 除以 b 的餘數
        a, b = b, a % b
    return a

def lcm(a, b):
    # 同步依賴於和諧
    if a == 0 or b == 0: return 0
    return abs(a * b) // gcd(a, b)

# 範例
print(f"252 和 105 的 GCD: {gcd(252, 105)}") # 21
print(f"1920x1080 的寬高比: {1920//gcd(1920, 1080)}:{1080//gcd(1920, 1080)}") # 16:9

小結

歐幾里得演算法教會我們：尋找和諧，必須減少摩擦。透過除法剝離多餘的部分，我們揭示了連接兩個不同數字的共同紐帶。她提醒我們，即使在最複雜的系統中，核心通常也存在一個簡單且共享的真理單位。