线性同余式与中国剩余定理

文︳张新春

线性同余式与中国剩余定理

文︳张新春

线性同余式

我们知道，18≡4（mod7）,于是，若将 x=6 代入3x≡4（mod7），同余式是成立的。我们就说x=6是线性同余式 3x≡4（mod7）的解。不难知道，6+7=13、6+14=20、6+21=27……也都是这个同余式的解。同样地，6-7=-1、6-14=-8、6-21=-15……也都是这个同余式的解。在这些解中，只需任取1个，就可以代表其他各解。

由于这里未知数的次数是1次，所以叫做一次同余式，也叫线性同余式。线性同余式的一般形式为 ax≡b（modk）。

这里，我们规定k＞0。

我们先来研究几个具体的线性同余式。

（1）2x≡1（mod3）

要找满足0≤x＜3的解，我们可以对该范围内的整数一一进行检验，不难发现x=2是该线性同余式的解。而且在这个范围内没有别的解。

（2）2x≡4（mod6）

我们对满足0≤x＜6的整数一一进行检验，可以发现x=2和x=5都是满足该线性同余式的解。而且这个范围内也没有别的解。

（3）2x≡1（mod4）

若检查满足0≤x＜4的整数，容易发现，其中没有满足2x≡1（mod4）的数。事实上，对于任意的整数x，2x是偶数，2x-1就是奇数，不可能被4整除，因此 2x≡1（mod4）无解。

从上面的实例可以发现，线性同余式有的无解，有的有唯一解，有的有多解。我们研究线性同余式，就是要研究如何判断一个线性同余式有没有解，如果有解，如何求出全部解。

若x满足线性同余式ax≡b（modk）。根据同余的意义，存在整数y，满足ax-ky=b。这就是一个线性不定方程。根据线性不定方程解存在的结论，只有当 a，k的最大公因数（a，k）能整除 b 时，上述线性不定方程才有解。并且解这个线性不定方程就可以得到x的值，从而得到线性同余式的解。

我们用这个方法来解一个线性同余式。

18x≡30（mod42）

首先，由于18和42的最大公因数为6，能整除30，因此，此线性同余式应该有解。

考虑线性不定方程18x-42y=30，即3x-7y=5。

我们通过观察可以知道， x=4，y=1，｛为一组特解。x=4就是线性同余式18x≡30（mod42）的一个解。

我们只关心x=4+7t（t为整数）。

对每一个确定的t，x=4+7t都应该是18x≡30（mod42）的解。

取定几个t的值，就可以得到一系列的解：4、11、18、25、32、39、46、53……

我们发现，46和4关于42同余，53和11也是这样。因此，线性同余式18x≡30（mod42）本质不同的解只有 6 个：4、11、18、25、32、39。而 18 与 30 的最大公因数恰好是6。于是，我们有以下结论：对于ax≡b（modk），令 a，k 的最大公因数为 g，则

（1）当 g不能整除 b时，ax≡b（modk）无解。

（2）当 g能整除 b时，ax≡b（modk）恰好有 g个本质不同的解。这g个本质不同的解为：x=x0+t·，其中x0为线性不定方程ax-ky=b的一个特解，t依次取 0，1，2，…，g-1。

这样，我们就完全把解ax≡b（modk）的问题转化成了解线性不定方程的问题。

中国剩余定理

中国剩余定理讨论的是线性同余式组的问题。

这个问题应当从《孙子算经》中的一道叫“物不知其数”的题谈起。“物不知其数”一题的原文是：今有物不知其数，三三数之剩二，五五数之剩三，七七数之剩二，问物几何？答曰：二十三。这道题的意思是说：有一堆东西不知道有多少个，如果三个三个地数，最后剩下两个；如果五个五个地数，最后剩下三个；如果七个七个地数，最后剩下两个，问这一堆东西有多少个。答案是二十三个。

所谓“三三数之剩二”，就是说物体的个数与2关于模3同余。“五五数之剩三，七七数之剩二”意思类似。若记物体的个数为x，以上三句分别对应着 x≡2（mod3），x≡3（mod5），x≡2（mod7）。

这就是线性同余式组。关于这个线性同余式组的解法，明朝数学家程大位在《算法统宗》中有一首歌诀：

三人同行七十稀，

五树梅花廿一枝，

七子团圆整半月，

除百零五便得知。

这首歌诀前三句中，每句都有两个数，每句的第一个数即3、5、7分别指的是线性同余式组的模，另外三个数是70、21和15。我们可列出算式：70×2+21×3+15×2=233。其中分别与 70、21和15相乘的2、3、2即是线性同余式组中与x同余的数。最后，将233减去105，减两次，得23，这就是答案。

这个解答中的关键是70、21和15这三个数。我们来看70，它满足两个条件：（1）它是5和7的公倍数；（2）它被 3 除余 1。所以，算式 70×2+21×3+15×2中的第一部分70×2被3除余2，而被5和7除都没有余数。

同样地，由于21是3和7的公倍数，且被5除余1，因此，70×2+21×3+15×2中的第二部分21×3被5除余3，而被3和7除都没有余数。类似地，这个算式的第三部分被7除余2，而被3和5除都没有余数。

简单地说，为了找到能被3除余2，被5除余3，被7除余2的数，我们先找到被3除余2的数，并且这个数被5和7除都没有余数，再找到被5除余3的数，并且这个数被3和7除都没有余数，最后找到被7除余2的数，并且这个数被3和5除都没有余数。此时，再把找到的这三个数加起来，就能满足要求。这是因为这三个数各满足一个条件而不影响其他条件。

我们把上述思考过程一般化，则有：

x≡b1（modm1），

x≡b2（modm2），

x≡b3（modm3）。

我们约定，这里的 m1，m2，m3两两互质。

我们先要找到一个被m1除余1的数（找到后再乘b1），但同时要求这个数必须是m2，m3的公倍数。由于 m1，m2，m3两两互质，m2，m3的公倍数即为m2m3的倍数，记m2m3M1，于是我们要找的数即为M1的倍数且被m1除余1。这事实上就是找一个 M1′，使 M1′M1≡1（modm1），相当于解线性同余式 M1x≡1（modm1）。注意到 M1，m1互质，上述线性同余式有解，即这个M1′是可以找到的。这时，M1′M1就是被 m1除余 1 而被 m2，m3除都没有余数的数。即 M1′M1b1被 m1除余 b1而被 m2，m3除没有余数。

在上面的具体线性同余式组中，M1=m2m3==35，M1′=2，M1′M1=70，M1′M1b1=70×2=140。

完全类似地，我们可以求出 M2′M2，M3′M3。这时 M1′M1b1+M2′M2b2+M3′M3b3即是符合要求的解。如果要找最小正整数解，就用这个数减去m1m2m3的某一个倍数即可。

对于更一般的线性同余式组，我们可以用类似的方法解决。上述解决问题的方法所产生的一般结果，就称为中国剩余定理。