關于一次同余方程組的探究

朱長新

摘? ?要：利用模運算的性質，給出了一個求解一次同余方程組的方法。該方法簡單且適用范圍廣，在一定程度上彌補了中國剩余定理的不足。

關鍵詞：同余方程組;乘法逆元;中國剩余定理

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.