文︳張新春

線性同余式與中國剩余定理

文︳張新春

線性同余式

我們知道，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個，就可以代表其他各解。

由于這里未知數(shù)的次數(shù)是1次，所以叫做一次同余式，也叫線性同余式。線性同余式的一般形式為 ax≡b（modk）。

這里，我們規(guī)定k＞0。

我們先來研究幾個具體的線性同余式。

（1）2x≡1（mod3）

要找滿足0≤x＜3的解，我們可以對該范圍內(nèi)的整數(shù)一一進行檢驗，不難發(fā)現(xiàn)x=2是該線性同余式的解。而且在這個范圍內(nèi)沒有別的解。

（2）2x≡4（mod6）

我們對滿足0≤x＜6的整數(shù)一一進行檢驗，可以發(fā)現(xiàn)x=2和x=5都是滿足該線性同余式的解。而且這個范圍內(nèi)也沒有別的解。

（3）2x≡1（mod4）

若檢查滿足0≤x＜4的整數(shù)，容易發(fā)現(xiàn)，其中沒有滿足2x≡1（mod4）的數(shù)。事實上，對于任意的整數(shù)x，2x是偶數(shù)，2x-1就是奇數(shù)，不可能被4整除，因此 2x≡1（mod4）無解。

從上面的實例可以發(fā)現(xiàn)，線性同余式有的無解，有的有唯一解，有的有多解。我們研究線性同余式，就是要研究如何判斷一個線性同余式有沒有解，如果有解，如何求出全部解。

若x滿足線性同余式ax≡b（modk）。根據(jù)同余的意義，存在整數(shù)y，滿足ax-ky=b。這就是一個線性不定方程。根據(jù)線性不定方程解存在的結(jié)論，只有當(dāng) a，k的最大公因數(shù)（a，k）能整除 b 時，上述線性不定方程才有解。并且解這個線性不定方程就可以得到x的值，從而得到線性同余式的解。

我們用這個方法來解一個線性同余式。

18x≡30（mod42）

首先，由于18和42的最大公因數(shù)為6，能整除30，因此，此線性同余式應(yīng)該有解。

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

我們通過觀察可以知道， x=4，y=1，｛為一組特解。x=4就是線性同余式18x≡30（mod42）的一個解。

我們只關(guān)心x=4+7t（t為整數(shù)）。

對每一個確定的t，x=4+7t都應(yīng)該是18x≡30（mod42）的解。

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

我們發(fā)現(xiàn)，46和4關(guān)于42同余，53和11也是這樣。因此，線性同余式18x≡30（mod42）本質(zhì)不同的解只有 6 個：4、11、18、25、32、39。而 18 與 30 的最大公因數(shù)恰好是6。于是，我們有以下結(jié)論：對于ax≡b（modk），令 a，k 的最大公因數(shù)為 g，則

（1）當(dāng) g不能整除 b時，ax≡b（modk）無解。

（2）當(dāng) g能整除 b時，ax≡b（modk）恰好有 g個本質(zhì)不同的解。這g個本質(zhì)不同的解為：x=x0+t·，其中x0為線性不定方程ax-ky=b的一個特解，t依次取 0，1，2，…，g-1。

這樣，我們就完全把解ax≡b（modk）的問題轉(zhuǎn)化成了解線性不定方程的問題。

中國剩余定理

中國剩余定理討論的是線性同余式組的問題。

這個問題應(yīng)當(dāng)從《孫子算經(jīng)》中的一道叫“物不知其數(shù)”的題談起?！拔锊恢鋽?shù)”一題的原文是：今有物不知其數(shù)，三三數(shù)之剩二，五五數(shù)之剩三，七七數(shù)之剩二，問物幾何？答曰：二十三。這道題的意思是說：有一堆東西不知道有多少個，如果三個三個地數(shù)，最后剩下兩個；如果五個五個地數(shù)，最后剩下三個；如果七個七個地數(shù)，最后剩下兩個，問這一堆東西有多少個。答案是二十三個。

所謂“三三數(shù)之剩二”，就是說物體的個數(shù)與2關(guān)于模3同余。“五五數(shù)之剩三，七七數(shù)之剩二”意思類似。若記物體的個數(shù)為x，以上三句分別對應(yīng)著 x≡2（mod3），x≡3（mod5），x≡2（mod7）。

這就是線性同余式組。關(guān)于這個線性同余式組的解法，明朝數(shù)學(xué)家程大位在《算法統(tǒng)宗》中有一首歌訣：

三人同行七十稀，

五樹梅花廿一枝，

七子團圓整半月，

除百零五便得知。

這首歌訣前三句中，每句都有兩個數(shù)，每句的第一個數(shù)即3、5、7分別指的是線性同余式組的模，另外三個數(shù)是70、21和15。我們可列出算式：70×2+21×3+15×2=233。其中分別與 70、21和15相乘的2、3、2即是線性同余式組中與x同余的數(shù)。最后，將233減去105，減兩次，得23，這就是答案。

這個解答中的關(guān)鍵是70、21和15這三個數(shù)。我們來看70，它滿足兩個條件：（1）它是5和7的公倍數(shù)；（2）它被 3 除余 1。所以，算式 70×2+21×3+15×2中的第一部分70×2被3除余2，而被5和7除都沒有余數(shù)。

同樣地，由于21是3和7的公倍數(shù)，且被5除余1，因此，70×2+21×3+15×2中的第二部分21×3被5除余3，而被3和7除都沒有余數(shù)。類似地，這個算式的第三部分被7除余2，而被3和5除都沒有余數(shù)。

簡單地說，為了找到能被3除余2，被5除余3，被7除余2的數(shù)，我們先找到被3除余2的數(shù)，并且這個數(shù)被5和7除都沒有余數(shù)，再找到被5除余3的數(shù)，并且這個數(shù)被3和7除都沒有余數(shù)，最后找到被7除余2的數(shù)，并且這個數(shù)被3和5除都沒有余數(shù)。此時，再把找到的這三個數(shù)加起來，就能滿足要求。這是因為這三個數(shù)各滿足一個條件而不影響其他條件。

我們把上述思考過程一般化，則有：

x≡b1（modm1），

x≡b2（modm2），

x≡b3（modm3）。

我們約定，這里的 m1，m2，m3兩兩互質(zhì)。

我們先要找到一個被m1除余1的數(shù)（找到后再乘b1），但同時要求這個數(shù)必須是m2，m3的公倍數(shù)。由于 m1，m2，m3兩兩互質(zhì)，m2，m3的公倍數(shù)即為m2m3的倍數(shù)，記m2m3M1，于是我們要找的數(shù)即為M1的倍數(shù)且被m1除余1。這事實上就是找一個 M1′，使 M1′M1≡1（modm1），相當(dāng)于解線性同余式 M1x≡1（modm1）。注意到 M1，m1互質(zhì)，上述線性同余式有解，即這個M1′是可以找到的。這時，M1′M1就是被 m1除余 1 而被 m2，m3除都沒有余數(shù)的數(shù)。即 M1′M1b1被 m1除余 b1而被 m2，m3除沒有余數(shù)。

在上面的具體線性同余式組中，M1=m2m3==35，M1′=2，M1′M1=70，M1′M1b1=70×2=140。

完全類似地，我們可以求出 M2′M2，M3′M3。這時 M1′M1b1+M2′M2b2+M3′M3b3即是符合要求的解。如果要找最小正整數(shù)解，就用這個數(shù)減去m1m2m3的某一個倍數(shù)即可。

對于更一般的線性同余式組，我們可以用類似的方法解決。上述解決問題的方法所產(chǎn)生的一般結(jié)果，就稱為中國剩余定理。