关于一次同余方程组的探究

朱长新

摘   要：利用模运算的性质，给出了一个求解一次同余方程组的方法。该方法简单且适用范围广，在一定程度上弥补了中国剩余定理的不足。

关键词：同余方程组;乘法逆元;中国剩余定理

1    一次同余方程组

同余是数论中的一个重要运算，在许多领域都有重要的应用t。关于同余方程的解法已有一些基本的结论。对于一次同余式的解的问题，已有下面的结果：

ax≡b（modm）， a≠0（modm）（1）

定理1：同余式（1）有解的充分与必要条件是gcd（a，m）/b，且在有解的情况下，方程的解为：

即方程的解数为gcd（a，m），其中x0是同余式（1）的一个特解。本文基于同余的简单性质，主要讨论的是k阶一次同余方程的解法。在我国古代的《孙子算经》里已经提出了这种形式的问题，并且得到了验证。这就是著名的中国剩余定理。

a1x≡b1（modm1），a2x≡b2（modm2），…，akx≡bk（modmk）

定理2：（中国剩余定理[1]）：设m1，m2，…，mk是k个两两互质的正整数，令m=m1m2…mk，且m=miMi，i=1，2，…，k，若a1=a2=…=ak=1，

則同余式（1）的解是：

X=M1'M1b1+M2'M2b2+…+Mk'Mkbk（modm）

其中M1'M1=1（modmi），i=1，2，…，k。

显然，上述中国剩余定理中a1=a2=…=ak=1和m1，m2，…，mk是k个两两互质的正整数，这两个条件比较苛刻，很多情形下难以满足。通过因子分解等手段可以将绝大部分的一次同余方程组化为满足中国剩余定理要求的形式[2]，一次同余方程组的阶数增大，导致计算的复杂程度增加。本文主要讨论一般情形下的同余方程组解法。

2    中国剩余定理的不足之处

中国剩余定理在数论中是个很重要的定理，应用于许多领域。但是，若从解同余方程组的角度来看，也存在一些不足之处，并非首选。文章就中国剩余定理的不足展开探讨，体现在如下3个方面。

2.1  标准化问题

在前面已经提到，求解同余方程组（1），首先要求各个元素ai（mod mi）的逆元，化成满足中国剩余定理所要求的形式，即：

x=a1-1b1（modm1），x=a2-1b2（modm2），…，x=ak-1bk（modmk）

根据欧几里得算法或是辗转相除法得到：若gcd（ai，mi）=1，则ak-1存在。因此，同余方程组（1）可用中国剩余定理求解的一个前提条件是：对于任意的1≤i≤k，均有gcd（ai，mi）=1。

2.2  符号与计算的不便

中国剩余定理直接给出了一定条件下同余方程组（1）的解，但引入的符号较多，如m，M以及M'等。关于同余式M1'M1=1（modmi）的解也不易计算（相对后面的解法），其中i=1，2，…，k，之后还需计算一个关于x的式子才可得到最终结果。因此，利用中国剩余定理求解同余方程组（1）会给计算带来不便[2]。

2.3  正整数mi（1≤i≤k）的两两互质问题

中国剩余定理的最大缺陷是要求不同的模数mi（1≤i≤k）必须两两互质。对于不互质的情形，在一定的条件下可以通过增加方程的个数，达到模数两两互质的要求，增加了计算的复杂程度。需要强调的是，中国剩余定理是中国人民的骄傲，它是一个非常重要的定理，在许多领域中都有重要的应用，上述所说的不足之处，主要是专门针对同余方程组的解法而言。

3    一般同余方程组的解法

基于中国剩余定理存在前面的一些不足，笔者试图寻找一般的解法进行解答。下面通过具体的实例来分析一次同余方程组的解法。

例1：求解下列同余方程组3x=2（mod 7），5x= 2（mod 11）。

分析：由于gcd（7，11）=1，所以只需将两个同余式中x前的系数化为1即可利用中国剩余定理求解。在此，我们利用定理1来求解。3-1=5（mod 7），3x=2（mod 7）等价于x=2×5=10=3（mod 7），通解为：

x=7t1+3，t1∈Z

将此解代入第二个同余式中，可得：

5x=5（7t1+3）=2（mod 11）

即2t1=9（mod 11）由2-1=6（mod 11）

故2t1=9（mod 11）等价于t1=6×9=54=10（mod 11），t1=11t2+10，t2∈Z。即同余方程组的通解为：

x=7t1+3=7（11t2+10）+3=77t2+73，t2∈Z

亦可表示为x=73（mod 7）。

通过例1可知，在解同余方程组时，没必要先将所有的同余方程式都化为标准型，即没必要将aix=bi（mod mi）化为x=ai-1bi（mod mi），其中1≤i≤k。

例2：求解下列同余方程组3x=1（mod 4），4x=6（mod 10）。

分析：由于gcd（4，10）=2，故不能利用中国剩余定理求解。在此，我们仍利用定理1来求解。验证3-1= 3（mod 4），3x=1（mod 4）等价x=1×3=3=3（mod 4），即通解为x=4t1+3，t1∈Z。将此解代入第二个同余式中，可得4x= 4（4t1+3）=6（mod 10），即6t1=4（mod 10）。

由于gcd（4，10）=2，故由定理（1）知，该同余式有两个解，下求其一特解。由6t1=4（mod 10），有3t1=2（mod 5），因此3-1=2（mod 5），所以3t1=2（mod 5）等价于t1=2×2=4（mod 5），即t1=5t2+4，t2∈Z。故x0=4是6t1=4（mod 10）的一特解，同余式的通解为t1=4+5s（mod 10），s=0，1。即同余方程组有两个解，且通解为：

x=4t1+3=4（10t2+4+5s）+40t2+19+20s，t2∈Z

同余方程组的通解亦可表示为x=19，39（mod 40）。

基于例2的解数可知，运用中国剩余定理不能求解此题，也就是说，上述解法比中国剩余定理简单且适用范围更广。

结合例1和例2的分析，我们不难看出，一次同余方程组的一般解法就是反复用一次同余式，直至求解出最后一个同余式的通解，可以验证此时所求出的同余式就是該同余式方程组的通解。同时，基于上述的例子可以看出，该方法在符号的引入和计算等方面都比中国剩余定理的求解更简单。更重要的是，该方法比中国剩余定理适用范围更大，可以说，此方法对每个同余式没有限制条件。

从上面的实例可知，在求解同余式时，主要涉及一个运算：求元素的乘法逆元，即对于给定的元素x，求y，使得xy=1（mod m）。由于所举的例子比较简单，一般通过简单的验证就可以确定一个元素的逆元。在一般情况下，需要通过辗转相除法求解。下面我们通过实例来说明这个求逆的方法。

例3：求137在模921下的逆元。

解：基于整数的除法，易得：

921=6×137+99，137=1×9+38，99=2×38+23，

37=1×2+15，23=1×15+8，15=1×8+7，8=1×7+1

进而可得：

1=8-7=8-（15-8）=2（23-15）-15=2×23-3（38-23）

=5（99-2×38）-3×38=5×9-13×38=5×99-13（137-99）

=8×9-13×137=8（921-6÷137）=-13×137

=18×921-121×137

即有：

=18×921-121×137=1

所以：

-121×137=1=1（mod 921）

故而：

137-1=-121=800（mod 921）。

[参考文献]

[1]闵嗣鹤，严士健.初等数论[M].第2版.南京：高等教育出版社，1982.

[2]潘承洞，潘承彪.简明数论[M].北京：北京大学出版社，1998.