ExtGcd

在數論和演算法競賽中，我們經常需要在模運算 (Modular Arithmetic) 的環境下進行除法。然而，模運算中沒有直接的除法操作。取而代之的是，我們需要找到一個數的「模乘法反元素」，並將除法轉換為乘法。

本文將介紹什麼是模乘法反元素，以及如何使用擴展歐幾里得算法 (Extended Euclidean Algorithm, ExtGcd) 來高效地找到它。

什麼是模乘法反元素？

對於兩個整數 a 和 m，如果存在一個整數 x 滿足以下同餘方程式：

a * x ≡ 1 (mod m)

那麼，我們稱 x 是 a 在模 m 下的模乘法反元素 (Modular Multiplicative Inverse)。

有了反元素 x，當我們想計算 b / a (mod m) 時，就可以轉換為計算 b * x (mod m)，從而實現模運算中的「除法」。

反元素的存在條件

並不是所有的 a 在模 m 下都有反元素。反元素存在的充分必要條件是 a 和 m 互質 (coprime)，也就是說它們的最大公因數 (Greatest Common Divisor, GCD) 為 1。

gcd(a, m) = 1

如果 gcd(a, m) ≠ 1，那麼 a 在模 m 下的乘法反元素不存在。

擴展歐幾里得算法 (ExtGcd)

擴展歐幾里得算法是歐幾里得算法的延伸。它不僅能計算出兩個整數 a 和 b 的最大公因數 d，還能同時找到一對整數 x 和 y，使得它們滿足貝祖定理 (Bézout’s identity)：

a * x + b * y = gcd(a, b)

如何利用 ExtGcd 找反元素？

現在，讓我們把這個公式與模乘法反元素的需求聯繫起來。我們想找的反元素 x 滿足：

a * x ≡ 1 (mod m)

這等價於存在一個整數 k，使得：

a * x = 1 + k * m

移項後得到：

a * x - k * m = 1

令 y = -k，上式變為：

a * x + m * y = 1

這和擴展歐幾里得算法的結果 a * x + m * y = gcd(a, m) 非常相似！

當 a 和 m 互質時，gcd(a, m) = 1，此時擴展歐幾里得算法給出的 x 和 y 正好滿足 a * x + m * y = 1。

對這個等式兩邊取模 m：

(a * x + m * y) mod m = 1 mod m
(a * x) mod m + (m * y) mod m = 1
a * x ≡ 1 (mod m)

瞧！擴展歐幾里得算法所求出的 x，正是 a 在模 m 下的乘法反元素。

需要注意的是，算法求出的 x 可能是負數。我們需要將其轉換為 [0, m-1] 範圍內的等價正整數，常用的方法是 (x % m + m) % m。

Python 實作

以下是使用 Python 實作的擴展歐幾里得算法，並用它來求解模乘法反元素。

def ext_gcd(a, b):
    """
    擴展歐幾里得算法
    返回 (gcd, x, y) 使得 a*x + b*y = gcd(a, b)
    """
    if b == 0:
        return a, 1, 0
    else:
        gcd, x, y = ext_gcd(b, a % b)
        # a*x + b*y = gcd(a,b)
        # b*x' + (a%b)*y' = gcd(b, a%b)
        # a%b = a - floor(a/b)*b
        # b*x' + (a - floor(a/b)*b)*y' = gcd
        # a*y' + b*(x' - floor(a/b)*y') = gcd
        # So, x = y', y = x' - floor(a/b)*y'
        return gcd, y, x - (a // b) * y

def mod_inverse(a, m):
    """
    計算 a 在模 m 下的乘法反元素
    """
    gcd, x, y = ext_gcd(a, m)
    if gcd != 1:
        # 反元素不存在
        raise ValueError(f"Inverse does not exist for a={a}, m={m} as gcd is {gcd}")
    
    # 將 x 調整到 [0, m-1] 的範圍內
    return (x % m + m) % m

# --- 範例 ---
a = 7
m = 26

try:
    inv = mod_inverse(a, m)
    print(f"{a} 在模 {m} 下的反元素是: {inv}")
    print(f"驗證: ({a} * {inv}) % {m} = {(a * inv) % m}")
except ValueError as e:
    print(e)

# --- 另一個範例 ---
a = 4
m = 10

try:
    inv = mod_inverse(a, m)
    print(f"{a} 在模 {m} 下的反元素是: {inv}")
except ValueError as e:
    print(e)

總結

模乘法反元素是模運算中不可或缺的工具，它讓我們能將除法問題轉化為乘法問題。透過擴展歐幾里得算法，我們可以在 a 和 m 互質的前提下，快速且有效地計算出反元素。這個算法不僅在理論上優雅，在實際應用（如密碼學、演算法競賽）中也扮演著關鍵角色。