扩展欧几里得算法与中国剩余定理

在《孙子算经》中有这样一个问题：有物不知其数，三三数之剩二，五五数之剩三，七七数之剩二。问物几何?

这个问题说的是，有一件物品，我们不知道它的数量。但是，如果三个三个数，最后会剩下两个；如果五个五个数，最后会剩下三个；如果七个七个数，最后会剩下两个。问这个东西的数量是多少？

实际上，这个问题在现在我们可以将其转化为一个同余方程组：

\[\left \{ \begin{aligned} x \equiv 2 \pmod 3 \\ x \equiv 3 \pmod 5 \\ x \equiv 2 \pmod 7 \end{aligned} \right.\]

中国剩余定理告诉了我们像这样的同余方程组的解。这个定理又称为孙子定理，通常被简写成CRT（Chinese Remainder Theorem）。

这篇文章将会从欧几里得算法开始讲起，之后过渡到扩展欧几里得算法解线性方程，最后介绍中国剩余定理。

欧几里得算法

欧几里得算法是用来计算最大公约数（greatest common divisor）的一个算法，它主要是基于下面这个递归式：

\[\text{gcd}(n, m) = \text{gcd}(m, n \bmod m)\]

如果这个式子成立的话，不断重复利用这个式子来计算，直到 $n$ 和 $m$ 中有一个数变为 $0$ 的时候，就可以求出了他们的最大公约数。

我来举个例子，比如说我们要求 $6$ 和 $15$ 的最大公约数，那么利用前面的式子就可以得到 $$ \text{gcd}(6, 15) = \text{gcd}(15, 6) = \text{gcd}(6, 3) = \text{gcd}(3, 0) = 3 $$

那么，如何证明这个式子呢？

我们可以设 $g = \text{gcd}(n, m)$，这样的话，对于右边的部分，$g \mid m$ 是显然的，至于 $g \mid (n \bmod m)$ 是否成立，我们可以根据 $$ n \bmod m = n - m\lfloor \frac{n}{m}\rfloor $$ 得出肯定的答案。这样我们就可以得到 $g \mid \text{gcd}(m, n \bmod m)$。

同样的，如果设 $g^\prime = \text{gcd}(m, n \bmod m)$，那么也可以得到 $g^\prime \mid g$

这样再根据整除关系的传递性，就可以得到 $g \mid g^\prime \mid g$。因此 $g$ 和 $g^\prime$ 必定相等。

int gcd(int n, int m)
{
	if(m == 0) return n;
	return gcd(m, n % m);
}

裴蜀定理

假设我们有一个关于 $x$ 和 $y$ 的线性方程 $ax + by = d$，现在要求判断这个方程是否存在整数解。

裴蜀定理告诉了我们，$ax + by = d$ 存在整数解当且仅当 $\text{gcd}(a, b) \mid d$。例如说 $3x + 6y = 2$ 就不存在整数解，$3x + 6y = 3$ 就存在整数解 $x = 1, y = 0$。

如何证明？ 显然 $\text{gcd}(a, b) \mid (ax + by)$，如果存在整数解的话必然有 $\text{gcd}(a, b) \mid d$，也就是说，如果 $\text{gcd}(a, b) \nmid d$ 这个线性方程就肯定不存在整数解。

那么在 $\text{gcd}(a, b) \mid d$ 的时候一定都存在整数解吗？我们来通过扩展欧几里得算法解释这个问题，实际上，扩展欧几里得算法的过程不仅回答了这个问题，而且还将解构造了出来。

扩展欧几里得算法

对于刚刚方程是否存在整数解的问题，我们只需要查看在 $d = \text{gcd}(a, b)$ 的时候是否存在整数解。也就是方程 $ax + by = \text{gcd}(a, b)$ 是否有整数解。

假设我们知道了方程 $bx + (a \bmod b)y = \text{gcd}(b, a \bmod b)$ 的一组整数解 $(x^\prime, y^\prime)$。

由于 $\text{gcd}(a, b) = \text{gcd}(b, a \bmod b)$，我们可以将上面两个方程联立起来，可以得到 $$ ax + by = bx^\prime + (a \bmod b)y^\prime $$

如果我们用 $a \bmod b = a - \lfloor \frac{a}{b} \rfloor b$ 来替换 $$ ax + by = bx^\prime + (a - \lfloor \frac{a}{b} \rfloor b)y^\prime $$ 再按照 $a$ 和 $b$ 来归类，就可以得到 $$ ax + by = ay^\prime + (x^\prime - \lfloor \frac{a}{b} \rfloor y^\prime)b $$

这样，$x = y^\prime$, $y = x^\prime - \lfloor \frac{a}{b} \rfloor y^\prime$ 一定会满足方程 $ax + by = \text{gcd}(a, b)$。这样我们就构造出了它的解。 同样按照欧几里得算法的递归过程一样，到边界的时候 $b = 0$，这时候整数解非常好找，就是 $x = 1, y = 0$。 这样我们就通过构造的方法证明了刚刚的裴蜀定理，同时也给出了一种计算线性方程的整数解的方法。

int exgcd(int a, int b, int& x, int& y)
{
	if(b == 0) 
	{
		x = 1, y = 0;
		return a;
	}

	int g = exgcd(b, a % b, x, y);
	int t = x;
	x = y;
	y = t - a / b * y;
	return g;
}

中国剩余定理

我们先来考虑只有两个方程，并且模数互质的情况。 假设现在有一个关于 $x$ 的同余方程组： \(\begin{equation} \label{z-raw} \left\{ \begin{aligned} x \equiv a_1 \pmod {p_1} \\ x \equiv a_2 \pmod {p_2} \end{aligned} \right. \end{equation}\)

我们如何解这个方程组呢？按照同余式的定义，我们知道上面这个方程组等价于 \(\begin{equation} \label{z} \left\{ \begin{aligned} x = a_1 + k_1p_1 \\ x = a_2 + k_2p_2 \end{aligned} \right. \end{equation}\)

其中 $k_1, k_2$ 是整数。 我们现在可以把 $(1)$ 中的两个方程联立起来，再消去 $x$。这样就会得到一个二元一次方程： $$ \begin{equation} \label{eqn-z-merge} a_1 + k_1p_1 = a_2 + k_2p_2 \end{equation} $$

这个方程是否存在整数解呢？根据裴蜀定理以及 $\text{gcd}(p_1, p_2) = 1$ 我们可以很容易就判断得到这个方程一定存在整数解，这样接着就可以直接利用扩展欧几里得算法来求出一组整数解，我们记为 $(k_1^\prime, k_2^\prime)$。之后随便利用一个解回代到 (2) 中，就可以得到了一个满足 (1) 的解，我们记为 $x_0$。

另外，根据 (3) 刚刚求出的一组解就可以的到它所有的整数解（注意在这里我们是假设 $p_1, p_2$ 互质的）： \(\left \{ \begin{aligned} k_1 = p_2t + k_1^\prime \\k_2 = p_1t + k_2^\prime \end{aligned} \right.\)

其中 $t$ 是任意整数。 这样代入 (2) 中就可以得到这个同余方程组所有的解： \(\begin{eqnarray*} x &=& a_1 + k_1p_1 \\ &=& a_1 + p_1p_2t + k_1^\prime \\ &=& x_0 + p_1p_2t \end{eqnarray*}\)

这个解实际上等价于下面这个同余方程： $$ x \equiv x_0 \pmod {p_1p_2} $$ 这时候，我们相当于把两个同余方程合并成为了一个。如果有多个同余方程的话，可以不断地选取两个方程，然后合并，之后用合并后的方程来替换原来的两个方程。每次进行一次合并方程的个数都会减少一个，这样如果有 $n$ 个方程，那么只需要合并 $n - 1$ 次就可以得到整个同余方程组的解了。

回顾刚刚的过程，对于一个同余方程组

\[\left\{ \begin{aligned} x &\equiv a_1 \pmod {p_1} \\ x &\equiv a_2 \pmod {p_2} \\ &\vdots \\ x &\equiv a_n \pmod {p_n} \end{aligned}\right.\]

在这里模数两两互质。

按照刚刚的过程合并完了之后可以得到一个同余方程

\(x \\equiv x_0 \\pmod {p_1p_2\\cdots p_n} \\)

这里 $x_0$ 表示合并过程中求出的一个满足上面同余方程的一个解。

这样，最后得到的一个同余方程实际上还告诉了我们一些信息：上面的同余方程组在 $[0, p_1p_2\cdots p_n)$ 这个区间内有且仅有一个解。

现在来看看如果模数不是两两互质的话该怎么办。

还是从只含有两个方程的同余方程组开始 \(\left\{ \begin{aligned} x \equiv a_1 \pmod {m_1} \\ x \equiv a_2 \pmod {m_2} \end{aligned}\right.\)

和先前一样，展开消去 $x$ 后得到 $$ \begin{equation} a_1 + k_1m_1 = a_2 + k_2m_2 \end{equation} $$

这时候这个方程是否一定有整数解就要稍加考虑了，同样的，还是根据裴蜀定理，我们可以知道如果 $\text{gcd}(m_1, m_2) \mid (a_2 - a_1)$ 那么这个方程就有整数解，否则它就不存在整数解。

那么在它存在整数解的时候，假设我们已经根据扩展欧几里得算法求出了一组特殊解 $(k_1^\prime, k_2^\prime)$，那么所有的解是什么呢？

我们设 $g = \text{gcd}(m_1, m_2)$，又由于 $a_2 - a_1$ 是 $g$ 的倍数，那么就可以把 (4) 这个方程改写为

\[\begin{equation} k_1\frac{m_1}{g} - k_2\frac{m_2}{g}=\frac{a_2 - a_1}{g} \end{equation}\]

这样的话 $\frac{m_1}{g}$ 和 $\frac{m_2}{g}$ 就互质了，那么这个方程所有的整数解就是

\[\left \{ \begin{aligned} k_1 = \frac{m_2}{g}t + k_1^\prime\\k_2 = \frac{m_1}{g}t + k_2^\prime \end{aligned} \right.\]

同样的，这里 $t$ 是任意整数。

这样类似刚刚往回代入可以得到

\[\begin{eqnarray*} x &=& a_1 + k_1m_1 \\&=& x_0 + \frac{m_1m_2}{g}t \\&=& x_0 + \text{lcm}(m_1, m_2)t \end{eqnarray*}\]

这个解实际上等价于下面这个同余方程： $$ x \equiv x_0 \pmod {\text{lcm}(m_1, m_2)} $$ 这样更完整的中国剩余定理就浮出水面了：

对于一个同余方程组

\[\left\{ \begin{aligned} x &\equiv a_1 \pmod {m_1} \\ x &\equiv a_2 \pmod {m_2} \\ &\vdots \\ x &\equiv a_n \pmod {m_n} \end{aligned}\right.\]

它等价于 $$ x \equiv x_0 \pmod {\text{lcm}(m_1, m_2, \cdots, m_n)} $$ 这里 $x_0$ 是这个方程的任意一个解，它可以通过刚刚的合并计算得到。

例如最开始的那个问题，它的同余方程组是：

\[\left\{ \begin{aligned} x &\equiv 2 \pmod 3 \\ x &\equiv 3 \pmod 5 \\ x &\equiv 2 \pmod 7 \end{aligned} \right.\]

首先我们对前两个方程进行计算，可以得到 $x \equiv 8 \pmod {15}$。那么，合并之后就可以得到

\[\left\{ \begin{aligned} x &\equiv 8 \pmod{15} \\ x &\equiv 2 \pmod 7 \end{aligned} \right.\]

再对这两个方程进行计算，之后可以得到 $$ x \equiv 23 \pmod {105} $$