中国剩余定理(CRT)

What · 是什么

中国剩余定理（CRT）求解一元线性同余方程组 x ≡ a_i (mod n_i)（i=1..k，模数两两互素），并保证在模 N=∏n_i 下有唯一解。解法：令 N_i=N/n_i，求 N_i 在模 n_i 下的逆元 inv_i，则 x ≡ Σ a_i·N_i·inv_i (mod N)。应用极广：大数取模分解（把模合数拆成互素因子再合并）、exLucas、组合数取模、『物不知数』类问题、公钥密码。模数不互素时用扩展 CRT（exCRT）：两两用扩展欧几里得合并方程。

Why · 为什么

How · 实现

伪代码

# CRT (模数两两互素)
def crt(a, n):        # a: 余数列表, n: 模数列表
  N = prod(n)
  x = 0
  for i in range(k):
    Ni = N // n[i]
    inv = mod_inverse(Ni, n[i])
    x += a[i] * Ni * inv
  return x % N

# exCRT (任意模数)
# 反复合并 (x mod cur_m) 与 (a_i mod n_i)
def ex_crt(a, n):
  x, m = 0, 1
  for ai, ni in zip(a, n):
    g, p, q = exgcd(m, ni)
    if (ai - x) % g: return None
    m2 = m // g * ni
    x = (x + (ai-x)//g * p % (ni//g) * m) % m2
    m = m2
  return x % m

Python 实现

from math import gcd


def egcd(a, b):
    """扩展欧几里得: 返回 (g, x, y) 使 a*x+b*y=g"""
    if b == 0:
        return a, 1, 0
    g, x1, y1 = egcd(b, a % b)
    return g, y1, x1 - (a // b) * y1


def mod_inverse(a, m):
    """a 在模 m 下逆元 (gcd(a,m)==1)"""
    g, x, _ = egcd(a, m)
    assert g == 1, "no inverse"
    return x % m


def crt(a, n):
    """CRT: 模数两两互素. 返回 x (0<=x<N) 满足 x≡a_i (mod n_i)."""
    N = 1
    for ni in n:
        N *= ni
    x = 0
    for ai, ni in zip(a, n):
        Ni = N // ni
        inv = mod_inverse(Ni, ni)
        x = (x + ai * Ni * inv) % N
    return x


def ex_crt(a, n):
    """exCRT: 任意模数(不要求互素). 无解返回 None; 否则返回最小非负解."""
    x, m = 0, 1
    for ai, ni in zip(a, n):
        g, p, _ = egcd(m, ni)
        if (ai - x) % g != 0:
            return None
        m2 = m // g * ni
        # (ai - x)/g * p 是 (m/g) 逆元的系数
        t = (ai - x) // g * p % (ni // g)
        x = (x + t * m) % m2
        m = m2
    return x % m


if __name__ == "__main__":
    # 物不知数: x≡2(3), x≡3(5), x≡2(7) => 最小 23
    assert crt([2, 3, 2], [3, 5, 7]) == 23
    # 另例: x≡1(2),2(3),3(5) => 最小解 23
    assert crt([1, 2, 3], [2, 3, 5]) == 23

    # CRT 与暴力枚举交叉验证 (互素模数)
    import random
    random.seed(83)

    def brute(a, n):
        N = 1
        for ni in n:
            N *= ni
        for x in range(N):
            if all(x % ni == ai for ai, ni in zip(a, n)):
                return x
        return None

    for _ in range(300):
        n = []
        while True:
            cand = random.randint(2, 12)
            if all(gcd(cand, x) == 1 for x in n):
                n.append(cand)
                if len(n) == 3:
                    break
        a = [random.randrange(ni) for ni in n]
        assert crt(a, n) == brute(a, n), (a, n)

    # exCRT 与暴力验证 (含不互素)
    for _ in range(400):
        n = [random.randint(2, 12), random.randint(2, 12), random.randint(2, 12)]
        a = [random.randrange(ni) for ni in n]
        sol = ex_crt(a, n)
        if sol is None:
            # 验证确实无解
            assert brute(a, n) is None, (a, n)
        else:
            assert all(sol % ni == ai for ai, ni in zip(a, n)), (a, n, sol)

    # 与 CRT 一致 (互素情形)
    a = [2, 3, 2]; n = [3, 5, 7]
    assert ex_crt(a, n) == crt(a, n) == 23
    # 无解情形: x≡1(2), x≡0(4) -> 无解
    assert ex_crt([1, 0], [2, 4]) is None
    print("All tests passed.")

易错点

• 用 CRT 前忘记检查模数两两互素（不互素用 exCRT）
• 求逆对象搞混：是对 N_i=N/n_i 求模 n_i 逆元，不是对 a_i
• a_i 未规范到 [0,n_i) 导致结果偏移
• exCRT 合并时 (ai-x) 可能为负，Python % 是余数语义需 % m2 归一
• 乘积 N 溢出（C++）或浮点；Python int 无此问题
• 无解判断：两两合并时 gcd 不整除 (a2-a1) 即无解

例题

信源

• OI Wiki✓ https://oi-wiki.org/math/number-theory/crt/
• CP-Algorithms✓ https://cp-algorithms.com/algebra/chinese-remainder-theorem.html
• 书籍✓ CPH ch21 Number theory (p207-216)