概念

中国剩余定理

模两两互素的同余方程组有唯一解（模乘积意义下），是中国古代数学的瑰宝，也是计算机大整数算术与并行计算的加速器。

阅读路径

参考可汗学院 Get ready 机制：先修概念 → 当前概念 → 进阶概念，✓ 表示已读。

中国剩余定理初等数论

01定义

对两两互素的模

m_1,\dots,m_k

，同余方程组

x\equiv a_i\pmod{m_i}

必有解，且解在模

M=\prod m_i

意义下唯一。构造：令

M_i=M/m_i

，

N_i

为

M_i

模

m_i

的逆元，则

x\equiv\sum a_iM_iN_i\pmod M

——环同构

\mathbb{Z}/M\mathbb{Z}\cong\prod_i\mathbb{Z}/m_i\mathbb{Z}

的显式见证。

两条剩余数列的周期交点在 15 内唯一出现一次

自然映射 $\mathbb{Z}/M\mathbb{Z}\to\prod_i\mathbb{Z}/m_i\mathbb{Z}$ （同时取余）在两两互素时是环同构：方程组有解即满射，模 $M$ 唯一即单射——「逐分量研究」合法化的普适理由。

$M_i=M/m_i$ 与其余模互素，故逆元 $N_i$ 存在； $x=\sum a_iM_iN_i$ 中第 $i$ 项模 $m_i$ 恰为 $a_i$ 、模 $m_j\ (j\neq i)$ 为 $0$ ——每个条件被「分工」满足。

《孙子算经》（约 4 世纪）「物不知数」：今有物不知其数，三三数之剩二，五五数之剩三，七七数之剩二——答曰二十三。秦九韶 1247 年《数书九章》给出大衍求一术（求模逆元），比高斯早五百年。

x\equiv a_i\pmod{m_i}\iff x\equiv\sum_{i=1}^{k}a_iM_iN_i\pmod M,\quad M_iN_i\equiv 1\pmod{m_i}

《孙子算经》载「物不知数」问题；秦九韶《数书九章》（1247）以大衍求一术系统求解并解算天文历法；高斯《算术研究》（1801）独立发现；现代将其视作中国数学对计算机科学的馈赠。

RSA 解密用 CRT 加速约 4 倍（分别模 p、q 运算再合并）、大整数运算的并行化、快速傅里叶变换的数论版本（NTT）、多项式插值与中国剩余码。

模 m₁、m₂ 的两列周期解的交点两组等差数列在 [0, m₁m₂) 内恰有一个公共点——这就是唯一解

m₁3m₂5a₁1a₂2