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

文︳張新春

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

文︳張新春

線性同余式

我們知道，18≡4（mod7）,于是，若將 x=6 代入3x≡4（mod7），同余式是成立的。我們就說(shuō)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。

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

（1）2x≡1（mod3）

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

（2）2x≡4（mod6）

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

（3）2x≡1（mod4）

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

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

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

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

18x≡30（mod42）

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

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

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

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

對(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）無(wú)解。

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

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

中國(guó)剩余定理

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

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

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

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

三人同行七十稀，

五樹(shù)梅花廿一枝，

七子團(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ù)。我們來(lái)看70，它滿(mǎn)足兩個(gè)條件：（1）它是5和7的公倍數(shù)；（2）它被 3 除余 1。所以，算式 70×2+21×3+15×2中的第一部分70×2被3除余2，而被5和7除都沒(méi)有余數(shù)。

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

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

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

x≡b1（modm1），

x≡b2（modm2），

x≡b3（modm3）。

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

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

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

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

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