一周一定理No.1 中国剩余定理

作者 | 林开亮

在最近推出的两篇文章

① 微积分之前奏1：高阶等差数列的求和

② 算命是胡扯，猜姓却不然

中，我们都提到了 中国剩余定理 ，虽然我曾在

从射雕到九章——在天大理学院物理系的通俗报告

介绍过，但有点浮光掠影，我们想在此详细介绍一下。

我们期待，本文作为 好玩的数学 开创的头一个专栏—— 一周一定理 ——的开篇，能够 打响第一炮 。本专栏的开创，学习和借鉴了下述网页（感谢上海交通大学数学系吴耀琨教授向我们推荐）

有兴趣的读者，可以先浏览这个主页上的各个定理。欢迎各位读者为本专栏供稿，投稿邮箱在这里 来，一起交流数学 。

好了，现在我们直奔主题。

中国剩余定理 ：设正整数m ₁ ，m ₂ ，…，m _n 两两互素，则下述同余方程组

（其中r ₁ ，r ₂ ，…，r _n 给定的整数）的整数解恰好是模

M=m ₁ m ₂ …m _n

的一个剩余类。事实上，方程 (*) 的通解为

x=r ₁ M ₁ x ₁ +…+r _n M _n x _n +kM，k∈Z  (#)

其中M _i =M/m _i ， 而x _i 是同余方程

M _i x _i ≡ 1(mod m _i )    (*i)

的一个特解，因而可以用求一术得出。

简单地说，中国剩余定理将一个同余方程组（*）的求解，归结为多个一次同余方程（*i)的求解，而后者可以用 求一术 来求解。那么，什么是求一术呢？我们表述成一个算法的形式：

求解方程

的整数解的求一术：

首先写出矩阵

然后对第一行两个元素辗转相除，并将对应的操作应用于第二行，直至第一行某个元素变成 0（停止信号） ，此时观察第一行的另一个元素：若它恰好是 1（正常信号） ，则它下方的那个数就是（♣）的一个特解；否则，（♣）无整数解。此外，若已得到（♣）的一个特解，比方说， ， 那么，（♣）的通解为

注 ：我们不打算证明求一术，它本质上就是解线性方程组的矩阵变换方法。我们指出，在中国古代还未出现0时，通常是用辗转相减（即“更相减损术”），所以最后终止的信号是，出现的等数（即最大公因子）为 1 ，这就是求 一 术名称的来由（对此，请参见许光午和李宝[4]）。另一方面，注意到方程（♣）本质上是在求逆，所以，也许一个更恰当的称谓是 求逆术 。由此可以理解，为什么在下述网页中，作者用了逆的记号来表述结果：

好了，现在我们来实战吧。首先，我们解释上述网页中的例子，即我们要求解同余方程组

为求解这个方程组，我们来求解两个更简单的方程组

与

先看（1），注意到（1）的第二个方程相当于说，x 是5的倍数，因此我们可以令

从而代入（1）的第一个方程，就把（1）整个转化为一次同余方程

在这个特殊情况，我们可以直接看出（1*）的一个特解为

类似的，我们来求解方程组(2), 注意到它的第一个方程相当于说

从而（2）可化为线性方程

容易观察到， （2*）的一个特解为

（注：当然你也可以取x ₂ =4，就像上述网页中那样）

因此，根据中国剩余定理，原方程组(0）的通解为

最经典的一个例子，即 金庸 曾在《射雕英雄传》原著中引用的“鬼谷算题”：

我们留给有兴趣的读者自行研究，其求解步骤，可以参考