3.1 中國剩餘定理#

概念說明#

《孫子算經》記載了一道名題：「今有物不知其數，三三數之剩二，五五數之剩三，七七數之剩二，問物幾何？」——某數除以 3 餘 2、除以 5 餘 3、除以 7 餘 2，求此數。答案是 23（加減 105 的倍數皆可）。能用一個「對 3、5、7 取餘」的通用解法正是中國剩餘定理（Chinese Remainder Theorem, CRT）。

定理內容：設模數 m₁, m₂, …, m_k 兩兩互質，則聯立同餘方程組 x ≡ a_i (mod m_i) 在模 M = m₁·m₂·…·m_k 下有唯一解。直觀原因是：每一餘數組合 (a₁, …, a_k) 對應 [0, M) 中恰好一個整數，資訊足夠、互不衝突。

CRT 的威力來自兩個方向：

合併：把「大模數下的運算」拆成數個小模數下並行的運算，最後再合併回來。RSA-CRT 解密把一次大模冪拆成兩次半大的模冪，速度約快 4 倍；多餘數系統（residue number system）乾脆拋棄進位，讓加法完全平行。
求解：許多數論演算法土法煉鋼只能算出「模小質數的答案」，先用多個質數取樣，再用 CRT 拼出模大數的答案。

演算法步驟#

求解 x ≡ a_i (mod m_i)（兩兩互質）： 1. 計算總模 M = ∏ m_i。 2. 對每個 i：M_i = M / m_i，並求 M_i 在模 m_i 下的反元素 y_i = M_i^(−1) mod m_i（用 2.2 節擴展歐幾里得）。 3. 解為 x = (∑ a_i · M_i · y_i) mod M。

背後的構造是「指示多項式」：e_i = M_i·y_i 滿足 e_i ≡ 1 (mod m_i) 且 e_i ≡ 0 (mod m_j)（j≠i），因此 ∑ a_i·e_i 恰好逐項命中各餘數。

兩模數不互質時仍可判斷：x ≡ a (mod m)、x ≡ b (mod n) 有解若且唯若 a ≡ b (mod gcd(m, n))，且解在模 lcm(m, n) 下唯一。

Python 程式碼範例#

from math import gcd, lcm

def ext_gcd(a, b):
    if b == 0:
        return (a, 1, 0)
    g, x1, y1 = ext_gcd(b, a % b)
    return (g, y1, x1 - (a // b) * y1)

def crt(pairs):
    """pairs: [(a1, m1), (a2, m2), ...]，模數兩兩互質，回傳最小非負解"""
    A = 0
    M = 1
    for a, m in pairs:
        g, p, q = ext_gcd(M, m)      # p*1 + q*0 的組合技巧直接解 x ≡ A (mod M), x ≡ a (mod m)
        if (a - A) % g != 0:
            return None               # 無解
        # 合併兩個方程：x = A + M*t，需 A + M*t ≡ a (mod m)
        t = ((a - A) // g) * p % (m // g)
        A = A + M * t
        M = lcm(M, m)
    return A % M

# 孫子算經原題：x%3=2, x%5=3, x%7=2
print(crt([(2, 3), (3, 5), (2, 7)]))        # 23
print(23 % 3, 23 % 5, 23 % 7)               # 2 3 2

# 不互質也能合併：x ≡ 7 (mod 15), x ≡ 4 (mod 10)？gcd(15,10)=5，7%5=2 ≠ 4%5=4，無解
print(crt([(7, 15), (4, 10)]))              # None
print(crt([(7, 15), (2, 10)]))              # 22（相容，模 30 唯一）

# 驗證：對模 5 與模 7 分別計算 x^10 mod 5、mod 7，CRT 合併 = 直接算 x^10 mod 35
x, e = 12, 10
r5 = pow(x, e, 5)
r7 = pow(x, e, 7)
print(crt([(r5, 5), (r7, 7)]), pow(x, e, 35))   # 兩者相同

# 應用：生日年份謎題 —— 模 6、7、11、13、17、19 各餘數已知，小於 1_000_000 的解唯一
pairs = [(2, 3), (3, 4), (2, 5), (1, 11), (6, 13), (9, 17)]
n = crt(pairs)
print(n, all(n % m == a for a, m in pairs))

複雜度分析#

逐一合併 k 個同餘式，每步一次擴展 gcd 與常數次乘法，總成本 O(k · log M) 的算術運算（以位數計則每步乘法為 O((log M)²)）。解的範圍是模 M = ∏ m_i，因此 k 個模數的資訊量是相乘的——模 3、5、7 共 105 種組合。這個「拆小再合併」的策略也是 RSA-CRT 的本質：模 N = pq 的解密指數運算拆成模 p 與模 q 兩半，各為半位數的模冪（成本約 1/4 倍），再以 CRT 合併，整體加速約 4 倍。注意當模數不互質時已不是唯一解問題，本節 crt 的合併版本會自動用 gcd 判斷相容性並以 lcm 合併，正是泛化情形。

練習#

用 CRT 求「除以 17 餘 11、除以 19 餘 3、除以 23 餘 7」的最小正整數，並驗證三個餘式皆成立。
寫函式 crt_pow(x, e, M, moduli)：把模 M（例如 2^200·3^100 之類可分解的大數）的冪運算拆成各模數下的小冪運算再 CRT 合併，並與 pow(x, e, M) 比對結果。
模 8 與模 12 的聯立同餘在哪些情況下有解？程式窮舉 x ∈ [0, 24)，把兩個餘數 (x%8, x%12) 列出來，觀察哪些餘數對出現、哪些不出現，並對照 gcd(8,12)=4 的相容條件。