中国剩余定理

问题形式

同余

对整数 \(m \geq 1\)，定义：

\[ x \equiv y \pmod m \Leftrightarrow m \mid (x - y) \]

模 \(m\) 意义下我们只关心正数落在了哪个同余类里。

核心问题

给定若干个同余方程（同余系统 / \(\text{congruence system}\)）:

\[ \begin{cases} x \equiv a_1 \pmod {m_1} \\ x \equiv a_2 \pmod {m_2} \\ x \equiv a_3 \pmod {m_3} \\ \vdots \\ x \equiv a_k \pmod {m_k} \end{cases} \]

我们要探索的问题是，是否存在整数 \(x\) 能同时满足所有方程？ 如果存在的话我们要如何构造出这个解？ 解在什么条件下是「唯一的」？

中国剩余定理

陈述

如果模数两两互质：

\[ \gcd(m_i,m_j) = 1 \ (i \neq j) \]

则同余系统：

\[ x \equiv a_i \pmod {m_i} \ (i = 1\dots k) \]

必定有解，而且解在模：

\[ M = \prod_{i=1}^k m_i \]

意义下唯一，也就是说如果 \(x\) 和 \(y\) 同时是方程的解， 那么必定有 \(x \equiv y \pmod M\)

构造性证明

我们令：

\[ M = \prod_{i=1}^k m_i,\ M_i = \frac{M}{m_i} \]

因为模数是两两互质的，也就是说我们对 \(M\) 进行只因子分解之后， 每个质因子只出现一次，那么我们除以掉 \(m_i\) 之后，\(M_i\) 里一定没有 \(m_i\) 这个质因子， 因此可以知道 \(\gcd(M_i,m_i) = 1\)， 那么 \(M_i\) 在模 \(m_i\) 的意义下是存在乘法逆元的：

\[ M_i^{-1} \pmod {m_i} \]

那么我们记逆元 \(t_i = M_i^{-1} \pmod {m_i}\)，即：

\[ M_i t_i \equiv 1 \pmod {m_i} \]

那么我们只需要构造：

\[ x \equiv \sum_{i=1}^k a_i M_i t_i \pmod M \]

构造正确性证明

对于这个东西，我们尝试对整个式子模 \(m_i\)：

\[ x \equiv (a_j M_j t_j \mod m_i) \pmod {m_i} \]

之后我们可以分两类讨论，\(j = i\) 和 \(j \neq i\)。

我们先考虑 \(j = i\) 的情况，这个比较简单：

因为根据我们上文定义 \(t_i\) 就是 \(M_i\) 在模 \(m_i\) 意义下的逆元，因此：

\[ M_i t_i \equiv 1 \pmod {m_i} \]

两边同时乘以 \(a_i\)：

\[ a_i M_i t_i \equiv a_i \pmod {m_i} \]

自然得证。

我们再考虑一下 \(i \neq j\) 的情况，这种情况的关键点在于 \(M_j\) 是必然含有因子 \(m_i\) 的， 这个东西很平凡，具体原因留给读者自行思考。

因为我们定义了 \(M = \prod_{r=1}^k\)，里面肯定是有一个因子 \(m_i\) 的。 而对于 \(M_j = M / m_j\)，当 \(j \neq i\) 时，我们除掉了 \(m_j\)，没有除掉 \(m_i\)， 而且因为模数两两互质，除掉 \(m_j\) 和 \(m_i\) 完全不相干。

因此 \(m_i \mid M_j\)，自然有：

\[ M_j \equiv 0 \pmod {m_i} \]

那我们带上 \(a_j\) 和 \(t_j\) 之后也必然有：

\[ a_j M_j t_j \equiv 0 \pmod {m_i} \]

这样一来所有 \(j \neq i\) 的项在模 \(m_i\) 之后就不见了。

于是对于模 \(m_i\)：

\[ x \equiv a_i + \underbrace{0 + 0 + \cdots + 0}_{j \ne i} \equiv a_i \pmod{m_i}. \]

综上所述，足以证明我们构造的 \(x\) 是可以同时满足所有方程的。

唯一性

当我们谈论中国剩余定理说到唯一性时，并不是说解只有一个整数， 而是只有一个模 \(M\) 的剩余类：

\[ x \equiv x_0 \pmod M \]

这一整个集合都是这个同余系统的解，只不过通常我们只取最小非负解 \(x \in [0,M-1]\)。

实现

要实现我们之前说的构造的话，显然我们需要计算出 \(M,M_i\)，同时还需要计算逆元 \(t_i \equiv M_i^{-1} \pmod m_i\)。 逆元的计算可以使用 \(\text{Exgcd}\)。

扩展中国剩余定理

然而，还有一些情况，我们会遇到模数并不两两互质的同余系统， 这个时候朴素的中国剩余定理就无法使用了，但我们依然可以通过某种手段来判断是否有解并尝试构造出解， 这就是 \(\text{exCRT}\)。

同余方程的合并

我们先来研究一个子问题：

\[ \begin{cases} x \equiv a \pmod m \\ x \equiv b \pmod n \end{cases} \]

我们记 \(g = \gcd(m,n)\)。

存在性

该同余系统有解，当且仅当：

\[ a \equiv b \pmod g \]

等价于 \(g \mid (b - a)\)。

必要性：如果 \(x \equiv a \pmod m\) 且 \(x \equiv b \pmod n\) 的话，那么：

\[ a-b \equiv x-x \equiv 0 \pmod g \Rightarrow g \mid (a - b) \]

之所以模数变成 \(g\)，是因为如果模 \(m\) 同余可以推出摸 \(m\) 的所有因子同余，而 \(g = \gcd(n,m)\)， 同时是 \(m\) 和 \(n\) 的因子，所以我们可以自然把模数变成 \(g\) 而且不破坏其正确性。

而对于充分性，会在构造的过程中自然得出。

构造解

根据 \(x \equiv a \pmod m\)，我们可以有：

\[ x = a + mt \]

我们代入第二个方程，则有：

\[ a + mt \equiv b \pmod n \Rightarrow mt \equiv (b - a) \pmod n \]

这就是一个线性同余方程，那么我们令：

\[ g = \gcd(m,n),\ m^{\prime} = \frac{m}{g}, \ n^{\prime} = \frac{n}{g}, \ c = \frac{b-a}{g} \]

若 \(g \nmid (b - a)\) 则无解， 如果有解的话，我们可以化简：

\[ m^{\prime} t \equiv c \pmod n^{\prime} \]

这个时候 \(\gcd(m^{\prime},n^{\prime}) = 1\)，因此 \(m^{\prime}\) 在 \(n^{\prime}\) 下有逆元 \((m^{\prime})^{-1}\)。

于是：

\[ t \equiv c \times (m^{\prime})^{-1} \pmod {n^{\prime}} \]

那么我们只需要取一个代表元 \(t_0\)，就可以得到一个解了：

\[ x_0 = a + mt_0 \]

合并

两个方程共同的周期是 \(\text{lcm}(m,n)\)，事实上合并之后的解集为：

\[ x \equiv x_0 \pmod {\text{lcm}(m,n)} \]

多个方程合并

对于同余系统：

\[ x \equiv a_i \pmod {m_i} (i=1\dots k) \]

我们的做法是维护一个当前状态下的合并结果：

\[ x \equiv A \pmod M \]

初始 \((A,M) = (a_1,m_1)\)，然后我们依次合并 \((a_2,m_2),(a_3,m_3)\dots\)。

当我们试图合并 \((a_i,m_i)\) 时， 我们令 \(g = \gcd(M,m_i)\)， 如果 \(A \not\equiv a_i \pmod g\) 则整体无解， 否则的话我们继续按照上一节所述，构造出 \(x_0\)，并且更新：

\[ (A,M) \Leftarrow (x_0, \text{lcm}(M,m_i)) \]

最后可以得到：

\[ x \equiv A \pmod M \]

即整个同余系统的解（如果存在的话）。

总结

综上所述，中国剩余定理和扩展中国剩余定理的时间复杂度瓶颈均来自 \(\text{Exgcd}\)，故复杂度为 \(O(\sum \log m_i)\)

日志

本页面创建于 2025/12/31 17:02

此文为 \(\text{24Records}\) 在 \(\text{2025}\) 年的最后一篇文章。

新年快乐。