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

张新春

线性同余式

我们知道，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，因此，此线性同余式应该有解。

对每一个确定的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）无解。

这样，我们就完全把解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除都没有余数。此时，再把找到的这三个数加起来，就能满足要求。这是因为这三个数各满足一个条件而不影響其他条件。

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