關(guān)于一次同余方程組的探究

朱長(zhǎng)新

摘? ?要：利用模運(yùn)算的性質(zhì)，給出了一個(gè)求解一次同余方程組的方法。該方法簡(jiǎn)單且適用范圍廣，在一定程度上彌補(bǔ)了中國(guó)剩余定理的不足。

關(guān)鍵詞：同余方程組;乘法逆元;中國(guó)剩余定理

1? ? 一次同余方程組

同余是數(shù)論中的一個(gè)重要運(yùn)算，在許多領(lǐng)域都有重要的應(yīng)用t。關(guān)于同余方程的解法已有一些基本的結(jié)論。對(duì)于一次同余式的解的問(wèn)題，已有下面的結(jié)果：

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

定理1：同余式（1）有解的充分與必要條件是gcd（a，m）/b，且在有解的情況下，方程的解為：

即方程的解數(shù)為gcd（a，m），其中x0是同余式（1）的一個(gè)特解。本文基于同余的簡(jiǎn)單性質(zhì)，主要討論的是k階一次同余方程的解法。在我國(guó)古代的《孫子算經(jīng)》里已經(jīng)提出了這種形式的問(wèn)題，并且得到了驗(yàn)證。這就是著名的中國(guó)剩余定理。

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

定理2：（中國(guó)剩余定理[1]）：設(shè)m1，m2，…，mk是k個(gè)兩兩互質(zhì)的正整數(shù)，令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。

顯然，上述中國(guó)剩余定理中a1=a2=…=ak=1和m1，m2，…，mk是k個(gè)兩兩互質(zhì)的正整數(shù)，這兩個(gè)條件比較苛刻，很多情形下難以滿足。通過(guò)因子分解等手段可以將絕大部分的一次同余方程組化為滿足中國(guó)剩余定理要求的形式[2]，一次同余方程組的階數(shù)增大，導(dǎo)致計(jì)算的復(fù)雜程度增加。本文主要討論一般情形下的同余方程組解法。

2? ? 中國(guó)剩余定理的不足之處

中國(guó)剩余定理在數(shù)論中是個(gè)很重要的定理，應(yīng)用于許多領(lǐng)域。但是，若從解同余方程組的角度來(lái)看，也存在一些不足之處，并非首選。文章就中國(guó)剩余定理的不足展開探討，體現(xiàn)在如下3個(gè)方面。

2.1? 標(biāo)準(zhǔn)化問(wèn)題

在前面已經(jīng)提到，求解同余方程組（1），首先要求各個(gè)元素ai（mod mi）的逆元，化成滿足中國(guó)剩余定理所要求的形式，即：

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

根據(jù)歐幾里得算法或是輾轉(zhuǎn)相除法得到：若gcd（ai，mi）=1，則ak-1存在。因此，同余方程組（1）可用中國(guó)剩余定理求解的一個(gè)前提條件是：對(duì)于任意的1≤i≤k，均有g(shù)cd（ai，mi）=1。

2.2? 符號(hào)與計(jì)算的不便

中國(guó)剩余定理直接給出了一定條件下同余方程組（1）的解，但引入的符號(hào)較多，如m，M以及M'等。關(guān)于同余式M1'M1=1（modmi）的解也不易計(jì)算（相對(duì)后面的解法），其中i=1，2，…，k，之后還需計(jì)算一個(gè)關(guān)于x的式子才可得到最終結(jié)果。因此，利用中國(guó)剩余定理求解同余方程組（1）會(huì)給計(jì)算帶來(lái)不便[2]。

2.3? 正整數(shù)mi（1≤i≤k）的兩兩互質(zhì)問(wèn)題

中國(guó)剩余定理的最大缺陷是要求不同的模數(shù)mi（1≤i≤k）必須兩兩互質(zhì)。對(duì)于不互質(zhì)的情形，在一定的條件下可以通過(guò)增加方程的個(gè)數(shù)，達(dá)到模數(shù)兩兩互質(zhì)的要求，增加了計(jì)算的復(fù)雜程度。需要強(qiáng)調(diào)的是，中國(guó)剩余定理是中國(guó)人民的驕傲，它是一個(gè)非常重要的定理，在許多領(lǐng)域中都有重要的應(yīng)用，上述所說(shuō)的不足之處，主要是專門針對(duì)同余方程組的解法而言。

3?   一般同余方程組的解法

基于中國(guó)剩余定理存在前面的一些不足，筆者試圖尋找一般的解法進(jìn)行解答。下面通過(guò)具體的實(shí)例來(lái)分析一次同余方程組的解法。

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

分析：由于gcd（7，11）=1，所以只需將兩個(gè)同余式中x前的系數(shù)化為1即可利用中國(guó)剩余定理求解。在此，我們利用定理1來(lái)求解。3-1=5（mod 7），3x=2（mod 7）等價(jià)于x=2×5=10=3（mod 7），通解為：

x=7t1+3，t1∈Z

將此解代入第二個(gè)同余式中，可得：

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

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

故2t1=9（mod 11）等價(jià)于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）。

通過(guò)例1可知，在解同余方程組時(shí)，沒必要先將所有的同余方程式都化為標(biāo)準(zhǔn)型，即沒必要將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，故不能利用中國(guó)剩余定理求解。在此，我們?nèi)岳枚ɡ?來(lái)求解。驗(yàn)證3-1= 3（mod 4），3x=1（mod 4）等價(jià)x=1×3=3=3（mod 4），即通解為x=4t1+3，t1∈Z。將此解代入第二個(gè)同余式中，可得4x= 4（4t1+3）=6（mod 10），即6t1=4（mod 10）。

由于gcd（4，10）=2，故由定理（1）知，該同余式有兩個(gè)解，下求其一特解。由6t1=4（mod 10），有3t1=2（mod 5），因此3-1=2（mod 5），所以3t1=2（mod 5）等價(jià)于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。即同余方程組有兩個(gè)解，且通解為：

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

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

基于例2的解數(shù)可知，運(yùn)用中國(guó)剩余定理不能求解此題，也就是說(shuō)，上述解法比中國(guó)剩余定理簡(jiǎn)單且適用范圍更廣。

結(jié)合例1和例2的分析，我們不難看出，一次同余方程組的一般解法就是反復(fù)用一次同余式，直至求解出最后一個(gè)同余式的通解，可以驗(yàn)證此時(shí)所求出的同余式就是該同余式方程組的通解。同時(shí)，基于上述的例子可以看出，該方法在符號(hào)的引入和計(jì)算等方面都比中國(guó)剩余定理的求解更簡(jiǎn)單。更重要的是，該方法比中國(guó)剩余定理適用范圍更大，可以說(shuō)，此方法對(duì)每個(gè)同余式?jīng)]有限制條件。

從上面的實(shí)例可知，在求解同余式時(shí)，主要涉及一個(gè)運(yùn)算：求元素的乘法逆元，即對(duì)于給定的元素x，求y，使得xy=1（mod m）。由于所舉的例子比較簡(jiǎn)單，一般通過(guò)簡(jiǎn)單的驗(yàn)證就可以確定一個(gè)元素的逆元。在一般情況下，需要通過(guò)輾轉(zhuǎn)相除法求解。下面我們通過(guò)實(shí)例來(lái)說(shuō)明這個(gè)求逆的方法。

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

解：基于整數(shù)的除法，易得：

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

進(jìn)而可得：

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）。

[參考文獻(xiàn)]

[1]閔嗣鶴，嚴(yán)士健.初等數(shù)論[M].第2版.南京：高等教育出版社，1982.

[2]潘承洞，潘承彪.簡(jiǎn)明數(shù)論[M].北京：北京大學(xué)出版社，1998.