整数中国剩余定理

把一个整数模各个 $n_i$ 的余数排成一列，就得到它的局部坐标。两两互素保证这些坐标可以任意组合：改变其中一个余数，不必连带改变其他余数。

显式公式中的 $N_i{u}_i$ 就是坐标选择器。它模 $n_i$ 等于 $1$，又因含有其他所有模数的因子，在其余坐标上等于 $0$。乘上 $a_i$ 并把各项相加，就逐个装入所需余数。这里逆元 $u_i$ 的存在来自 $gcd(N_i,n_i)=1$，可由 Bézout 等式求得。

若 $x,y$ 都是解，每个 $n_i$ 都整除公理库整除Divisibility存在整数倍关系时定义的二元关系。 $x-y$。由于模数两两互素，它们的乘积 $N$ 也整除 $x-y$，这就说明了为什么解在模 $N$ 意义下唯一。

两条同余怎样归并 ​

先考虑 $x\equiv a(\mathrm{mod}m)$、$x\equiv b(\mathrm{mod}n)$，其中 $m,n>0$。令 $d=gcd(m,n)$。若 $x$ 存在，则 $d$ 同时整除 $x-a$ 与 $x-b$，必有 $d\mid (b-a)$。这一步给出了无需寻找 $x$ 就能检查的必要条件。

反过来，若 $d\mid (b-a)$，用扩展 Euclidean 算法公理库整数欧几里得算法Euclidean algorithm for integers反复使用带余除法计算最大公约数的有限算法。求出 $um+vn=d$，置

新增项是 $m$ 的倍数，所以第一条同余保持成立；模 $n$ 时 $mu\equiv d$，于是新增项恰好把余数从 $a$ 改为 $b$。这便直接构造出一个解。两个解之差必须同时被 $m,n$ 整除，故全部解为 $x_0+\mathrm{lcm}(m,n)\mathbb{Z}$，其中 $\mathrm{lcm}(m,n)=mn/d$。

把 $x=a+mt$ 代入，也能把这一步写为

约去 $d$ 后的 $m/d$ 才与新模数互素；在原模数 $n$ 下直接求 $m$ 的逆元可能根本不可行。若 $n/d=1$，则 $n\mid m$，相容性已保证第二条是第一条的后果，直接保留 $x\equiv a(\mathrm{mod}m)$ 即可。

为什么任意有限多条只需两两检查 ​

必要性仍来自解之差。充分性的关键是：同一个素数的幂次约束可以排成一条从弱到强的链。对每个整除 $L$ 的素数 $p$，取所有 $n_i$ 中出现的最大幂次 $p^{E_p}$，并选一条含有这个幂次的模数 $n_{i(p)}$。先要求

不同素数对应的 $p^{E_p}$ 两两互素，已证的互素 CRT 因而给出一个 $x$。现在检查任意原条件 $x\equiv a_j(\mathrm{mod}{n}_j)$：若 $p^e$ 是 $n_j$ 的素数幂分量，则 $e\le E_p$，且 $p^e\mid gcd(n_j,n_{i(p)})$。两两相容保证 $a_j\equiv a_{i(p)}(\mathrm{mod}{p}^e)$，所以构造出的 $x$ 满足 $n_j$ 的每个素数幂分量，也就满足模 $n_j$ 的整条条件。

若 $L=1$，所有条件本来就没有限制；否则上述构造涵盖 $L$ 的全部素因子。最后，两个解之差被每个 $n_i$ 整除，等价于被 $L$ 整除，便得到一般版本的唯一性。实际计算时不必先分解全部模数：维护已合并的 $(A,M)$，逐条执行前面的二式归并即可；充分性证明保证两两相容的输入不会在中途出现矛盾。

从一个同余式代入另一个 ​

求解

设 $x=1+4k$，则 $4k\equiv 1(\mathrm{mod}9)$；因为 $4^{-1}\equiv 7(\mathrm{mod}9)$，得 $k\equiv 7(\mathrm{mod}9)$，于是

回代检查：$29=4\cdot 7+1=9\cdot 3+2$，两个余数都正确。全部整数解为 $29+36t$，其中 $t\in \mathbb{Z}$。

模数共享因子时，余数也要相容 ​

共同因子记录了两条条件重叠的信息，它们在这部分必须给出相同答案。

例如 $x\equiv 1(\mathrm{mod}4)$ 与 $x\equiv 3(\mathrm{mod}6)$ 都要求 $x$ 为奇数，因此相容。把 $x=1+4k$ 代入第二式，得到 $4k\equiv 2(\mathrm{mod}6)$，即 $2k\equiv 1(\mathrm{mod}3)$，所以 $k\equiv 2(\mathrm{mod}3)$，最终 $x\equiv 9(\mathrm{mod}12)$。相反，$x\equiv 0(\mathrm{mod}2)$ 与 $x\equiv 1(\mathrm{mod}4)$ 分别要求偶数与奇数，因而无解。

“两两互素”要求每一对模数的最大公因数都为 $1$。例如 $6,10,15$ 的共同最大公因数为 $1$，但每一对仍共享一个素因子；这时应使用上述兼容性判据和最小公倍数。

三条相容条件与一张矛盾证书 ​

继续求

前两条合并为 $x\equiv 9(\mathrm{mod}12)$。第三条与它的公因数为 $4$，而 $5-9=-4$ 可被 $4$ 整除。由 $12-8=4$，取归并公式中的 $u=1$，得到

故全部解为 $x\equiv 21(\mathrm{mod}24)$。逐条验算，$21$ 除以 $4,6,8$ 的余数确实为 $1,3,5$。周期是 $24$；模数乘积 $192$ 会把同一个解族拆成八个余类，不能再声称模乘积唯一。

若只把第三条改为 $x\equiv 4(\mathrm{mod}8)$，便不必继续计算。第一条要求 $x\equiv 1(\mathrm{mod}4)$，第三条却要求 $x\equiv 0(\mathrm{mod}4)$；等价地，$gcd(4,8)=4$ 不整除余数差 $4-1=3$。这一对冲突条件就是无解的证书。

计算模 $N$ 的和或积时，可以分别在较小的模数 $n_i$ 下计算，再用 CRT 恢复结果。各坐标能够并行处理，这正是多精度运算和 RSA 私钥运算加速中使用它的原因。同余方程计数也由此转化为各坐标解数的乘积。

互素整数版本是环的中国剩余定理公理库环上的中国剩余定理Chinese remainder theorem for rings两两互素理想的交商与对应商环直积之间存在规范同构。的特例：这里的互素条件由最大公因数公理库最大公约数Greatest common divisor · GCD同时整除两个整数且被所有公约数整除的非负整数。判定，在一般交换环中则改为理想之和等于整个环。若模数不互素，任意余数组合都可拼接的结论已不适用，还需用前面的 Bézout 归并或素数幂论证建立相容性判据。将整数模数换成互素多项式后，同样的拼接思路还可用于插值和模多项式计算。

拼接还解释了合数模平方根为何可能多于两个。求 $x^2\equiv 1(\mathrm{mod}15)$，等价于分别求模 $3$、模 $5$ 的平方根。每边都有 $1,-1$ 两种选择，CRT 把四种符号组合分别还原为 $1,4,11,14$；每个根都对应唯一一对局部符号。二次剩余公理库二次剩余Quadratic residue模奇素数同余于某个平方的非零剩余类。中奇素数模下的“两个根”，正是在此被两个独立坐标组合成了四个根。

固定一个素数 $p$ 并依次处理模 $p,p^2,\dots$ 时，问题变成无限相容精度，而非有限个互素坐标的自由拼接。p-adic 整数公理库p-adic 整数与数p-adic integers and numbers · p进整数与数用相容余数构造 p-adic 整数环与数域，以有界进位证明有理数恰有最终周期的数字展开，并计算精确截断误差。容纳所有这样的相容系统；每一层有整数代表，并不保证存在一个普通整数满足全部无限条件。