中国剩余定理

概述

中国剩余定理（Chinese Remainder Theorem, CRT）是数论中关于联立同余方程组的核心定理：当模数 $m_{1}, m_{2}, \dots, m_{n}$ 两两互素时，同余方程组 $x \equiv a_{i} (mod m_{i})$ 在模 $m = m_{1} m_{2} \dots m_{n}$ 下有唯一解。CRT 提供了两种求解方法——构造法（利用模逆元将各方程的贡献叠加）和回代法（逐步代入消元）。该定理在大整数算术加速、RSA 解密优化、秘密共享方案等领域有广泛应用，其历史可追溯至中国南北朝时期的《孙子算经》。

定义

中国剩余定理（Chinese Remainder Theorem, CRT）

设 $m_{1}, m_{2}, \dots, m_{n}$ 为两两互素的正整数（ $> 1$ ）， $a_{1}, a_{2}, \dots, a_{n}$ 为任意整数。则同余方程组

$⎩ ⎨ ⎧ x \equiv a_{1} (mod m_{1}) x \equiv a_{2} (mod m_{2}) ⋮ x \equiv a_{n} (mod m_{n})$

在模 $m = m_{1} m_{2} \dots m_{n}$ 下有唯一解。

构造法证明：令 $M_{k} = m / m_{k}$ （即除 $m_{k}$ 外所有模数的乘积）。因为 $g cd (m_{k}, M_{k}) = 1$ ，存在 $M_{k}$ 模 $m_{k}$ 的逆元 $y_{k}$ ，使得 $M_{k} y_{k} \equiv 1 (mod m_{k})$ 。构造解：

$x = a_{1} M_{1} y_{1} + a_{2} M_{2} y_{2} + \dots + a_{n} M_{n} y_{n}$

验证：对每个 $k$ ，当 $j \neq = k$ 时 $M_{j} \equiv 0 (mod m_{k})$ ，因此 $x \equiv a_{k} M_{k} y_{k} \equiv a_{k} \cdot 1 \equiv a_{k} (mod m_{k})$ 。

$■$

回代法求解

回代法（back substitution）通过逐步代入消元来求解同余方程组：

由第一个方程 $x \equiv a_{1} (mod m_{1})$ ，令 $x = m_{1} t + a_{1}$

代入第二个方程，解关于 $t$ 的同余方程，得到 $t \equiv t_{0} (mod m_{2})$

令 $t = m_{2} u + t_{0}$ ，代入第三个方程，以此类推

最终得到 $x$ 关于最后一个参数的表达式，即为通解

核心性质

性质	描述	说明
前提条件	模数 $m_{1}, \dots, m_{n}$ 两两互素	不满足此条件时不能直接使用 CRT
解的存在性	方程组必有解	在两两互素条件下
解的唯一性	模 $m = m_{1} \dots m_{n}$ 下唯一	最小非负解在 $[0, m)$ 中
构造法	$x = \sum a_{k} M_{k} y_{k}$	需要计算 $n$ 个模逆元
回代法	逐步代入消元	每步解一个线性同余方程
大整数表示	余数向量唯一表示	$(a mod m_{1}, \dots, a mod m_{n})$
并行运算	分量独立运算后 CRT 恢复	可加速大整数算术

关系网络

graph TB
    A["中国剩余定理 CRT"] --> B["线性同余方程"]
    A --> C["模逆元"]
    A --> D["同余"]
    A --> E["RSA密码系统"]

    A --> F["构造法求解"]
    A --> G["回代法求解"]
    A --> H["大整数算术"]

    F --> F1["计算 M_k = m/m_k"]
    F --> F2["求 M_k 模 m_k 的逆元 y_k"]
    F --> F3["x = Σ a_k M_k y_k"]

    G --> G1["逐步代入消元"]
    G --> G2["每步解线性同余方程"]

    H --> H1["余数向量表示"]
    H --> H2["分量并行运算"]
    H --> H3["CRT 恢复结果"]

    style A fill:#5cb85c,color:#fff
    style B fill:#4a90d9,color:#fff
    style C fill:#d9534f,color:#fff
    style D fill:#e8a838,color:#fff
    style E fill:#9b59b6,color:#fff

线性同余方程是 CRT 的基础构件：CRT 求解联立的多个线性同余方程
模逆元是 CRT 构造法的核心工具：需要计算 $M_{k}$ 模 $m_{k}$ 的逆元 $y_{k}$
同余提供了 CRT 的理论基础：模运算的基本性质保证构造法的正确性
RSA密码系统利用 CRT 加速解密：将模 $n = pq$ 的运算分解为模 $p$ 和模 $q$ 的运算

章节扩展

第4章：数论与密码学

中国剩余定理是第 4.4 节的重要内容，连接了同余方程求解与实际应用：

4.4 解同余方程：CRT 是线性同余方程组求解的系统化方法，构造法与回代法两种途径
4.4 大整数算术：利用 CRT 将大整数运算分解为小模数的并行运算，最后恢复结果
4.4 费马小定理：与 CRT 联合应用可简化复杂的大幂计算
4.6 密码学：RSA 解密利用 CRT 将模 $n$ 的运算分解为模 $p$ 和模 $q$ ，加速约 4 倍

补充

中国剩余定理的历史与推广

中国剩余定理的最早形式可追溯至中国南北朝时期的《孙子算经》（约公元 3—5 世纪），其中记载了著名的”物不知数”问题：“有物不知其数，三三数之剩二，五五数之剩三，七七数之剩二。问物几何？“该问题在 1247 年由南宋数学家秦九韶在《数书九章》中给出了系统化解法，称为”大衍求一术”。在西方，该定理由欧拉（Euler）于 18 世纪重新发现并严格证明。在抽象代数中，CRT 有深刻的环论推广：当理想 $I_{1}, \dots, I_{n}$ 两两互素时， $R / (I_{1} \cap \dots \cap I_{n}) ≅ R / I_{1} \times \dots \times R / I_{n}$ 。在现代计算机科学中，CRT 被广泛应用于大整数运算加速、秘密共享方案（Shamir’s Secret Sharing）以及 RSA 解密优化等领域。

学术来源：Rosen, K. H. (2019). Discrete Mathematics and Its Applications (8th ed.). McGraw-Hill, Section 4.4, Theorem 2.

参考链接：Chinese Remainder Theorem - Wikipedia

参见

线性同余方程 — CRT 求解的基础构件
模逆元 — CRT 构造法中计算 $M_{k}$ 模 $m_{k}$ 的逆元
同余 — CRT 的理论基础
RSA密码系统 — 利用 CRT 加速 RSA 解密运算

CS Wiki

探索

中国剩余定理

中国剩余定理

定义

核心性质

关系网络

章节扩展

第4章：数论与密码学

补充

参见

关系图谱

目录

反向链接