形式陈述

若正整数 $n_1,\dots,n_k$$n_1,\dots ,n_k$ 两两互素，则对任意整数 $a_1,\dots,a_k$$a_1,\dots ,a_k$，同余组

$$ x\equiv a_i\pmod{n_i}\qquad(1\le i\le k) $$$$x\equiv a_i(\mathrm{mod}{n}_i)(1\le i\le k)$$

存在解，并且所有解模

$$ N=n_1n_2\cdots n_k $$$$N=n_1{n}_2\cdots n_k$$

唯一。令 $N_i=N/n_i$$N_i=N/n_i$，取 $u_i$$u_i$ 满足 $N_iu_i\equiv1\pmod{n_i}$$N_i{u}_i\equiv 1(\mathrm{mod}{n}_i)$，则

$$ x\equiv\sum_{i=1}^k a_iN_iu_i\pmod N $$$$x\equiv \sum _{i=1}^k{a}_i{N}_i{u}_i(\mathrm{mod}N)$$

给出显式解。等价地，环同态

$$ \mathbb Z/N\mathbb Z\longrightarrow\prod_i\mathbb Z/n_i\mathbb Z $$$$\mathbb{Z}/N\mathbb{Z}⟶\prod _i\mathbb{Z}/n_i\mathbb{Z}$$

是同构。

直觉

两两互素的模数提供彼此独立的坐标。每个 $N_iu_i$$N_i{u}_i$ 在第 $i$$i$ 个坐标等于一、在其余坐标等于零，像离散的坐标选择器。

例子与边界

$x\equiv2\pmod3$$x\equiv 2(\mathrm{mod}3)$、$x\equiv3\pmod5$$x\equiv 3(\mathrm{mod}5)$ 的解为 $x\equiv8\pmod{15}$$x\equiv 8(\mathrm{mod}15)$。若模数不互素，方程组有解当且仅当 $a_i\equiv a_j\pmod{\gcd(n_i,n_j)}$$a_i\equiv a_j(\mathrm{mod}gcd(n_i,n_j))$ 对所有 $i,j$$i,j$ 成立；解若存在，模最小公倍数唯一。例如 $x\equiv0\pmod2$$x\equiv 0(\mathrm{mod}2)$ 与 $x\equiv1\pmod4$$x\equiv 1(\mathrm{mod}4)$ 不相容。两两互素比“整体 gcd 为一”更强，三个模数整体 gcd 为一并不足以直接使用乘积模结论。显式公式中的逆元存在正因 $\gcd(N_i,n_i)=1$$gcd(N_i,n_i)=1$。

推论与应用

CRT 用于大整数并行模运算、有限环分解、插值、秘密分享和密码实现加速。

参考资料

• Kenneth Ireland and Michael Rosen, A Classical Introduction to Modern Number Theory, 2nd ed., Springer, 1990，Ch. 2, Chinese remainder theorem。
• Ivan Niven, Herbert S. Zuckerman, and Hugh L. Montgomery, An Introduction to the Theory of Numbers, 5th ed., Wiley, 1991，Ch. 2, simultaneous congruences。