中国剩余定理，顺带着exgcd求逆元

 

“有物不知其数。三三数之剩二，五五数之剩三，七七数之剩二，问物几何？”

这道题非常的古老。

把他转化成现代数学表示就是

$$\begin{cases} x\equiv 2\pmod3 \\ x\equiv 3\pmod5 \\ x \equiv 2\pmod7 \end{cases}$$

然后让我们求 。

我们把它转化为以下式子（其中 序列两两互质）：

$$\begin{cases} x\equiv r_1\pmod {m_1} \\ x\equiv r_2\pmod {m_2} \\ x\equiv r_3\pmod {m_3} \\ \cdots \\ x\equiv r_n\pmod {m_n} \end{cases}$$

(记住这个两两互质！！！)

就变成了一般的中国剩余定理。

一般中国剩余定理解法

1. 首先求出 。
2. 然后令 。
3. 求出 在 mod 意义下的逆元 。
4. 最后答案 就等于 。

如何证明？

我们先不考虑这个 mod，

证明：当 时，原式子成立。

因为 是一堆 的和，所以对于 对应的某一个 和 ，我们分情况讨论：

• 当 时，因为根据 的定义并且 ，他包含了 。所以 。所以 。
• 当 时， 在 mod 意义下的逆元一定存在。所以 。

$$\begin{equation} \begin{aligned} x &\equiv \sum_{i=1}^{n} r_i c_i p_i &\pmod {m_j}\\ &\equiv r_j c_j p_j & \pmod {m_j}\\ &\equiv r_j &\pmod {m_j} \end{aligned} \end{equation}$$

于是对于某一个 和 成立。而又因为 未定，所以其实对于所有的 都成立。所以原式子成立。

Q.E.D.

那么加了 mod M 之后的呢？

因为 mod M 相当于是减去 的整数倍，对余数没有任何影响。对上述式子也成立。

就这样就证明完了！

……

坏了，搞忘逆元怎么求了！

exgcd 求逆元

众所周知，考试中用的最多的求逆元的方式就是快速幂求逆元。但是快速幂求逆元有一个缺点，就是那个 “mod 意义下” 的那个 ，他只能是质数！

所以要引用另外一种求逆元的方式：Exgcd！

exgcd 的本职工作是求出 的整数解的。但是因为逆元的定义是 ，所以把他转化一下，就变成了：。就变成了上面这个样子。因为有逆元的条件就是互质，所以它们的 gcd 自然就是 。所以只需带入，然后求出上面的那个 就可以了。

下文将讲一般的 exgcd。

首先一般的 gcd 是怎么求的？那就是 。

那么这个 exgcd 其实也和上面的差不多，也是推到底了之后递归算。

手推一下就行。分两种情况：

• 如果 ，那么就说明 就是原来的最大公因数了。那么此时的方程就变成了 。很明显，。
• 如果 ，那么就可以从上一层递归过来。具体步骤如下：

$$\begin{equation} \begin{aligned} ax + by &= \gcd(a, b) \\ &= \gcd(b, a \bmod b) \\ &= bx_0 + (a \bmod b)y_0 &（这里设上一层的解为x_0和y_0）\\ &= bx_0 + (a - \lfloor a/b \rfloor b)y_0 \\ &= bx_0 + ay_0 - \lfloor a/b \rfloor by_0 \\ &= ay_0 + b(x_0 - \lfloor a/b \rfloor y_0) \\ \end{aligned} \end{equation}$$

即可得出。

然后一层一层递归就行。

---

好。那回到正题。回到中国剩余定理。

那么要是 序列不是两两互质的话呢？

那么就只能用到扩展中国剩余定理了！

扩展中国剩余定理

现在不互质，就不能用求逆元的方法了，因为根本没有逆元！

那就用逐个合并的方法。

我们先来看前两个：

$$\begin{cases} x\equiv r_1 \pmod {m_1} \\ x\equiv r_2 \pmod {m_2} \end{cases}$$

发现它们两个可以变为不定方程：

$$\begin{cases} x = m_1p+r_1 \\ x = m_2q+r_2 \end{cases}$$

然后合并成：

$$m_1p - m_2q = r_2 - r_1$$

这时我们要求出 和 这两个未知量。

根据裴蜀定理（不定方程 有解当且仅当 ）可得：

• 当 时，原方程无解。
• 当 时，原方程有解。此时可以用上文所述的 exgcd 求得此解。

求出 exgcd 里面的解是 了之后（因为说 exgcd 求出的其实是 的一组解），就可以得出（后面都用 代替 ）：

真正的特解 。

它们 和 的通解：

$$P = p+ \frac{m_2}{\gcd} \times k, Q = q + {\frac{m_1}{\gcd }} \times k$$

所以 。

于是可以转化为一个同余方程式：$x \equiv m_1 p + r_1 \pmod{\text{lcm}(m_1, m_2)}$

这就又变回原来的那样了！

于是我们可以一个一个合并下去，直到最终，求出答案。

Auth0r: Tofsox