線性同余式與中國(guó)剩余定理

張新春

線性同余式

我們知道，18≡4（mod7），于是，若將x=6代入3x≡4（mod7），同余式是成立的。我們就說x=6是線性同余式3x≡4（mod7）的解。不難知道，6+7=13、6+14=20、6+21=27……也都是這個(gè)同余式的解。同樣地，6-7=-1、6-14=-8、6-21=-15……也都是這個(gè)同余式的解。在這些解中，只需任取1個(gè)，就可以代表其他各解。

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

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

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

（1）2x≡1（mod3）

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

（2）2x≡4（mod6）

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

（3）2x≡1（mod4）

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

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

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

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

18x≡30（mod42）

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

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

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

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

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

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

中國(guó)剩余定理

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

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

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

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

三人同行七十稀，

五樹梅花廿一枝，

七子團(tuán)圓整半月，

除百零五便得知。

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

這個(gè)解答中的關(guān)鍵是70、21和15這三個(gè)數(shù)。我們來看70，它滿足兩個(gè)條件：（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ù)。類似地，這個(gè)算式的第三部分被7除余2，而被3和5除都沒有余數(shù)。

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

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