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

張新春

線性同余式

我們知道，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ù)線性不定方程解存在的結論，只有當a，k的最大公因數(shù)（a，k）能整除b時，上述線性不定方程才有解。并且解這個線性不定方程就可以得到x的值，從而得到線性同余式的解。

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

18x≡30（mod42）

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

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

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

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

（1）當g不能整除b時，ax≡b（modk）無解。

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

中國剩余定理

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

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

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

這就是線性同余式組。關于這個線性同余式組的解法，明朝數(shù)學家程大位在《算法統(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，這就是答案。

這個解答中的關鍵是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ù)各滿足一個條件而不影響其他條件。

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