第 6 章：中国剩余定理与余数坐标

返回目录

6.1 定理怎样合并多个同余条件

设 $m_1,\ldots,m_k$ 是两两互质的正整数， $M=m_1\cdots m_k$ 。中国剩余定理（CRT）说：给定任意余数 $a_1,\ldots,a_k$ ，同余组

$x\equiv a_i\pmod{m_i}\qquad(1\le i\le k)$

有解，而且模 $M$ 只有一个解。也就是说，答案可以有很多个整数代表，但它们都相差 $M$ 的倍数。

“两两互质”是每一对不同模数的最大公约数都为1。它使各个同余要求之间没有共同因子造成的冲突，也保证完整周期是乘积 $M$ 。

6.2 为什么存在：构造只影响一个坐标的项

令 $M_i=M/m_i$ 。由于模数两两互质， $M_i$ 与 $m_i$ 互质，所以有逆元 $t_i$ 满足 $M_it_i\equiv1\pmod{m_i}$ 。

现在看 $E_i=M_it_i$ ：它对 $m_i$ 余1，对所有其他 $m_j$ 余0，因为 $M_i$ 含有 $m_j$ 这个因子。于是

$x=\sum_{i=1}^k a_iE_i$

对 $m_j$ 取模时，除第 $j$ 项以外都消失，只留下 $a_j\cdot1$ 。所以这个 $x$ 同时满足全部要求。这不是单纯记一个求和公式，而是在构造“只负责一个余数条件”的项，再把它们相加。

6.3 为什么唯一，以及为什么可以使用两个坐标

若 $x,y$ 都满足全部同余，所有 $m_i$ 都整除 $x-y$ 。因为 $m_i$ 两两互质，它们的乘积 $M$ 也整除 $x-y$ ，即 $x\equiv y\pmod M$ 。这就证明模 $M$ 的唯一性。

特别地，若 $p,q$ 是不同质数，模 $n=pq$ 的每个剩余类都唯一对应一对坐标：

$x\bmod n\quad\longleftrightarrow\quad(x\bmod p,\ x\bmod q).$

任意一对坐标都能合起来，合起来的类又只有一个，这就是双射。加法、乘法、取幂都可以在两个坐标分别进行，再合并结果。

例如模55的34对应 $(4,1)$ ，也就是模5为 $-1$ 、模11为1。计算 $34^2$ 时，两边分别平方都得到1，CRT就保证 $34^2\equiv1\pmod{55}$ 。这个例子只用于展示坐标的含义；一般结论是上面的双射。

如果 $x$ 与 $pq$ 互质，两个坐标都非零；反过来，两坐标都非零也意味着 $x$ 与 $pq$ 互质。因此CRT还给出 $U_{pq}\longleftrightarrow U_p\times U_q$ 。第9章会用它解释随机底数为什么产生独立坐标。

6.4 模数不互质时怎样修改

对于 $x\equiv a\pmod m$ 、 $x\equiv b\pmod n$ ，若 $m,n$ 不互质，两个要求可能冲突。正确的相容条件是

$\gcd(m,n)\mid(b-a).$

必要性很直接： $x-a$ 被 $m$ 整除， $x-b$ 被 $n$ 整除，所以二者都被最大公约数整除，相减得到 $b-a$ 也必须被它整除。

充分性可由线性同余看出。令 $c=\gcd(m,n)$ ，先写 $x=a+mk$ ，代入第二个条件得到 $mk\equiv b-a\pmod n$ 。若 $c\mid(b-a)$ ，把整除关系中的三项都除以 $c$ ，就得到模 $n/c$ 的同余； $m/c$ 与 $n/c$ 互质，可以用逆元解出 $k$ 。解的周期是 $\operatorname{lcm}(m,n)=mn/c$ ，这里 $\operatorname{lcm}$ 表示最小公倍数。