中国剩余定理 (CRT)

玩一玩

找出所有$a$，使得满足下列关系式：
$$ \begin{aligned} a & \equiv 3\;(\text{mod}\;5) \\ a & \equiv 2\;(\text{mod}\;7) \end{aligned} $$

通过暴力枚举，我们可以得知答案：
$$ a = 23 + 35k\;(k \in Z) $$

简单形式

现在来考虑一个问题：

证明：一定存在一个$a$，满足
$$a \equiv a_1\;(\text{mod}\;m) \\a \equiv a_2\;(\text{mod}\;n)$$

其中$m \bot n$

我们使用鸽巢原理来证明。
设有$n$个数模$m$等于$a_1$，这$n$个数是：
$$ a_1,\;m + a_1,\;2m + a_1,\;\dots,\;(n - 1)m + a_1 $$

即设其中有两个数模$n$意义下同余，设它们为$im + a_1$和$jm + a_1$ ($i < j$)。
那么意味着：
$$ jm + a_1 = pn + r \\ im + a_1 = qn + r $$

两式相减可得：
$$ (j - i)m = (p - q)n $$

因为$p - q \in Z$，所以$n \mid (j - i)m$。
但是$m \bot n$，且$0 \lt j - i \le n - 1$，所以$n \not\mid (j - i)m$，与之前的假设相矛盾。
故之前选出的$n$个数里面没有两个数在模$n$意义下同余。
那么这里面必定存在一个数模$n$余$a_2$。

中国剩余定理

证明：存在一个数$x$，满足
$$x \equiv a_1 \; (\text{mod}\;m_1) \\x \equiv a_2 \; (\text{mod}\;m_2) \\\dots \\x \equiv a_k \; (\text{mod}\;m_k)$$

其中$m_1,\;m_2,\;\dots,\;m_k$两两互质

当然可以考虑两两合并的方式，并使用之前鸽巢原理的证法来证明。
当然我们考虑一种更具有价值的证法。
既然要证明其存在，不如直接构造一个答案：
首先设：
$$ M = \prod_{j=1}^k m_j \tag{2.1} $$

是所有模数之积。

$$ M_i = {M \over m_i} \tag{2.2} $$

是剔除掉某一个模数的积。

$$ C_i = M_i(M_i^{-1}\;\text{mod}\;m_i) \tag{2.3} $$

则是一个神奇的数字。
由于$M_i$肯定与$m_i$互质，所以这个逆元是肯定能求出来的。
那么：
$$ x \equiv \sum_{i=1}^k a_iC_i \; (\text{mod}\;M) $$

接下来就是要证明这个数同时满足上面的方程。
首先注意到：
$$ m_i \mid C_j \Longrightarrow C_i \equiv 0 \; (\text{mod}\;m_i) \;\;\; (i \neq j) $$

同时：
$$ C_i \equiv M_i\cdot M_i^{-1} \equiv 1 \; (\text{mod}\;m_i) $$

于是：
$$ x \equiv a_i \; (\text{mod} \; m_i) $$

因此这个数是满足要求的。
同时我们获得了中国剩余定理 (CRT) 的公式：
$$ x = \sum_{i=1}^k a_i M_i(M_i^{-1}\;\text{mod}\;m_i) \tag{2.4} $$

借助欧几里德算法，可以在$O(n\log n)$的时间内计算答案。

应用

中国剩余定理一个最大的应用就是计算一些数在模一个合数下的取值。
例如，求大组合数取模：
$$ {n \choose m} \;\text{mod}\; p $$

对于这个问题，如果$p$是质数且比较小，我们可以采用Lucas定理求解。
然而现在是合数。
我们考虑一种方案，将合数$p$进行质因数分解，这样就可以分解成多个质数，对于每一个质数，我们都有方法求解答案。这样对于每一个质数计算答案之后，我们得到了一个模线性方程组。
这样就变成了我们之前所讨论的问题。对于此，使用中国剩余定理，就可以合并答案。