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

文︳張新春

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

文︳張新春

線性同余式

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

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

這里，我們規定k＞0。

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

（1）2x≡1（mod3）

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

（2）2x≡4（mod6）

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

（3）2x≡1（mod4）

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

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

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

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

18x≡30（mod42）

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

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

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

我們只關心x=4+7t（t為整數）。

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

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

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

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

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

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

中國剩余定理

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

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

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

這就是線性同余式組。關于這個線性同余式組的解法，明朝數學家程大位在《算法統宗》中有一首歌訣：

三人同行七十稀，

五樹梅花廿一枝，

七子團圓整半月，

除百零五便得知。

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

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

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

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

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

x≡b1（modm1），

x≡b2（modm2），

x≡b3（modm3）。

我們約定，這里的 m1，m2，m3兩兩互質。

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

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

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

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