中国剩余定理

1.中国剩余定理要解决的问题

假设现在有一个未知整数$x$，满足

$$\begin{cases} x\equiv2\pmod3,\\ x\equiv3\pmod5,\\ x\equiv2\pmod7 \end{cases}$$

中国剩余定理想要解决的问题就是：

知道一个数对几个不同模数的余数，能不能把原来的数重新拼回来？

答案是：当这些模数两两互素时，可以。

2.中国剩余定理的正式内容

假设$m_1,m_2,\ldots,m_k$两两互素，也就是$\gcd(m_i,m_j)=1\qquad(i\ne j).$

那么对于任意余数 $a_1,\ldots,a_k$，方程组

$$\begin{cases} x\equiv a_1\pmod{m_1},\\ x\equiv a_2\pmod{m_2},\\ \vdots\\ x\equiv a_k\pmod{m_k} \end{cases}$$

一定有解，而且这个解在模

$$M=m_1m_2\cdots m_k$$

的意义下是唯一的。

“模 $M$ 唯一”不是说只有一个整数解，而是说所有解都是

$$x=x_0+nM,\qquad n\in\mathbb Z.$$

例如如果 $x_0=23,M=105$，那么$23,128,233,338,\ldots$其实是同一个模 $105$ 的解。

3. 一个直观例子

回到开头的问题，求满足

$$\begin{cases} x\equiv2\pmod3,\\ x\equiv3\pmod5,\\ x\equiv2\pmod7 \end{cases}$$

的 $x$。

因为 $3,5,7$ 两两互素，所以 CRT 告诉我们：

• 一定有解；
• 解在模 $3\cdot5\cdot7=105$ 下唯一。

我们当然可以先试着找：

满足第一条的数是$2,5,8,11,14,17,20,23,\ldots$

其中除以 $5$ 余 $3$ 的有$8,23,38,\ldots$

再检查模 $7$：$23\equiv2\pmod7.$

所以$\boxed{x\equiv23\pmod{105}}.$

但枚举只适合很小的数字。CRT 真正重要的是它给出了一套系统的构造方法。

4. 思路：构造CRT 基底

假设现在有三个数 $s_1,s_2,s_3$，使得

$$\begin{array}{c|ccc} &\bmod3&\bmod5&\bmod7\\ \hline s_1&1&0&0\\ s_2&0&1&0\\ s_3&0&0&1 \end{array}$$

我们假设$x=2s_1+3s_2+2s_3$，那$x$是不是现在就满足：

$$\begin{cases} x=2s_1+3s_2+2s_3\equiv2+0+0=2\pmod3, \\x=2s_1+3s_2+2s_3\equiv0+3+0=1\pmod5, \\ x=2s_1+3s_2+2s_3\equiv0+0+2=1\pmod7 \end{cases}$$

我们就得到了$x$。那下面我们来看怎么构造三个基底。

---

构造 $s_1$

要让它模 $5$、模 $7$ 都等于 $0$，最简单的，直接取

$$5\cdot 7=35,$$

现在 $35\equiv2\pmod3$，我们要把这个 $2$ 调整成 $1$。

因为

$$2\cdot2\equiv1\pmod3,$$

所以取

$$s_1=35\cdot2=70.$$

验证：

$$70\equiv1\pmod3,\qquad 70\equiv0\pmod5,\qquad 70\equiv0\pmod7.$$

---

构造 $s_2$

思路同上，先取另外两个模数的乘积：$3\cdot7=21.$

因为

$$21\equiv1\pmod5,$$

所以直接取

$$s_2=21.$$

---

构造 $s_3$

先取$3\cdot5=15.$

因为$15\equiv1\pmod7,$

所以取

$$s_3=15.$$

5. 用基底把余数拼起来

现在有了基底，我们构造

$$\begin{aligned} x &= 2s_1+3s_2+2s_3 \\ &=2\cdot70+3\cdot21+2\cdot15 \\ &=140+63+30 \\ &=233. \end{aligned}$$

因为我们计算的$x$是模$3\cdot5\cdot7=105$的，所以将它化到 $0\le x<105$：$233\equiv23\pmod{105}.$

我们就得到

$$\boxed{x\equiv23\pmod{105}}.$$

验证一下模 $3$ 时：

$x=2s_1+3s_2+2s_3 \equiv2\cdot1+3\cdot0+2\cdot0 =2\pmod3.$

模 $5$ 和模 $7$ 时同理。

6. 一般的 CRT 公式

设模数为 $m_1,\ldots,m_k$，令

$$M=m_1m_2\cdots m_k,\qquad M_i=\frac{M}{m_i}.$$

因为 $M_i$ 与 $m_i$ 互素，所以 $M_i$ 在模 $m_i$ 下有逆元。找一个 $u_i$，使得

$$u_iM_i\equiv1\pmod{m_i}.$$

然后定义

$$s_i=u_iM_i.$$

这个 $s_i$ 自动满足

$$s_i\equiv1\pmod{m_i},$$

而对于 $j\ne i$，

$$s_i\equiv0\pmod{m_j}.$$

因此方程组的解是

$$\boxed{ x\equiv a_1s_1+a_2s_2+\cdots+a_ks_k\pmod M }.$$

还是用上面的例子

此时模数是$m_1=3$，$m_2=5$，$m_3=7$，令

$$M=3\cdot 5\cdot 7=105, \\\quad M_1=\frac{105}{3}=35,\quad M_2 = \frac{105}{5}=21,\quad M_3 = \frac{105}{7}=15$$

找到$u_1=2$，$u_2=1$，$u_3=1$，那么$s_1=2\cdot35=70$，$s_2=21$，$s_3=15$，

题中的余数$a_1=2$，$a_2=3$，$a_3=2$。

得到$x=2\cdot 70 + 3\cdot 21 + 2\cdot 15 = 233\equiv 23 \pmod{105}$

7. 为什么解一定“唯一”

假设 $x$ 和 $y$ 都满足同一组余数条件，那么对每个 $i$ 都有

$$x\equiv y\pmod{m_i}.$$

因此

$$m_i\mid(x-y).$$

也就是说，$x-y$ 同时能被所有 $m_i$ 整除。由于这些模数两两互素，它们的乘积也整除 $x-y$：

$$M=m_1\cdots m_k\mid(x-y).$$

所以

$$x\equiv y\pmod M.$$

这就是“模 $M$ 唯一”。

8. 为什么要求模数两两互素

如果模数不互素，任意余数组合就不一定有解。

例如

$$x\equiv0\pmod2,\qquad x\equiv1\pmod4.$$

第一条说 $x$ 是偶数，第二条说 $x$ 除以 $4$ 余 $1$，也就是奇数，两者矛盾，所以没有解。