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

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

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

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

 \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)

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

我来举个例子,比如说我们要求 615 的最大公约数,那么利用前面的式子就可以得到

 \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。因此 gg^\prime 必定相等。

裴蜀定理

假设我们有一个关于 xy 的线性方程 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

再按照 ab 来归类,就可以得到

 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

这样我们就通过构造的方法证明了刚刚的裴蜀定理,同时也给出了一种计算线性方程的整数解的方法。

中国剩余定理

我们先来考虑只有两个方程,并且模数互质的情况。

假设现在有一个关于 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_1g 的倍数,那么就可以把 (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}

Miskcoo's Space,版权所有丨如未注明,均为原创
转载请注明转自:http://blog.miskcoo.com/2014/09/chinese-remainder-theorem

miskcoo

顺利从福州一中毕业!感觉大学周围都是聚聚十分可怕QAQ 想要联系的话欢迎发邮件:miskcoo [at] gmail [dot] com

4 thoughts on “扩展欧几里得算法与中国剩余定理

  1. 对于一般不互素的思路应该是 2 化 1 的思路来做比较好即

    x = a \bmod m

    x = b \bmod n

    m u  + a = n v + b mu - nv = b - a 然后

    于是有解当且仅当 \text{gcd}(m,n) |(b-a) 。用exgcd 求一个解 u,v 出来,然后就知道 x 的一个解 x_0

    最终原式等价于 x = x_0 \bmod \text{lcm}(m,n)

    而对于n个这样的同余方程,就一个个的化最终化为1个的形式也就是最终的解了。当然miskcoo大神应该只是不想写0.0

Leave a Reply

Your email address will not be published. Required fields are marked *

NOTE: If you want to add mathematical formulas, use $$ to wrap them. For example, use $$x_0$$ to get $$x_0$$.

If you want to get a newline, hit Enter twice, that is, use double newlines to get a newline.