詳析孫子定理

趙云平

【摘要】孫子定理在各版本的初等數論教材中均有介紹，但細節不夠明確，使讀者在學習過程中產生很多疑問，本文在給出孫子定理的基礎上，通過實例詳細分析了孫子定理的算法，讓更多的讀者受益.

【關鍵詞】孫子定理;同余式;一次同余式組

孫子定理在數論及近世代數學領域是非常重要的理論，起著基礎作用，所解決的問題是求未知量的系數為1，模兩兩互質的一次同余式的解.它在國際上被稱為中國剩余定理或中國余數定理，是數論中一個重要定理，定理的構造值得仔細推敲.求解一個未知數聯立同余式組，通常應用“孫子定理”，這是初等數論教材中介紹的主要算法.

1 基本概念

定義1[1] 給定一個正整數m，把它叫作模.如果用m去除任意兩個整數a和b，所得余數相同，稱a與b關于模m同余，記作a≡b（mod m）.若余數不同，稱a與b關于模m不同余，記作a≠b（mod m）.

定義2[2] 設f（x）=anxn+an-1xn-1+…+a0，其中ai是整數，m是一個正整數，就把f（x）=anxn+an-1xn-1+…+a0≡0（mod m）叫作模m的同余式，n就叫作這個同余式的次數.

定理1[2] 一次同余式ax≡b（mod m），當（a，m）=1時，有唯一解.

定理2[2] （a，b）=1存在整數s，t，使as+bt=1.

定理3（傳遞性）[4] 如果a≡b（mod m），b≡c（mod m）a≡c（mod m）.

2 孫子定理

定理4（孫子定理）[1-6] 設m1，m2，…，mk是k個兩兩互質的正整數，

M=m1m2·…·mk=∏ki=1mi，Mi=Mmi，i=1，2，…，k，則同余式組x≡b1（mod m1），x≡b2（mod m2），…，x≡bk（mod mk）的解是x≡M′1M1b1+M′2M2b2+…+M′kMkbk（mod m），其中Mi′Mi≡1（mod mi），i=1，2，…，k.列表如下：

這個孫子定理就給出了求解一次同余式組的一般算法，這是關于模m的運算.

3 具體算法與實例

這個方法具體是什么呢？來看幾個例子.

例1 求解同余式組

x≡1（mod 3），x≡-2（mod 5），x≡4（mod 11）.

分析 把它列成一個表，大體上就是這樣一個算法.

它有這樣幾項，除數、余數、最小公倍數、衍數、乘率、各總、答數，最后還可以求出最小答數.這里除數分成三個，除數分別是3，5，11，余數分別是1，-2，4，衍數是什么呢？如果對應除數3，那就是另外兩個除數相乘，那就是5×11，對應除數5的就是3×11，對應除數11的就是3×5;來看這個乘率，就是1，2，3，這個所謂乘率是什么呢？求乘率稍麻煩一點，就是讓衍數5×11=55乘上x關于模3余1的解，即55x≡1（mod 3），這個式子的解怎么求？因為（55，3）=1，1|1有解，實際上就是轉化為求二元一次不定方程55s+3t=1的解，這種方法過程不夠簡便，那這個一次同余式里邊，怎么方便地求出x呢？首先把55除以3，商18余1，所以55x≡1（mod 3）就變成了x≡1（mod 3），這是因為55≡1（mod 3），又x≡x（mod 3），有55x≡x（mod 3），又根據同余的傳遞性，所以x≡1（mod 3）;另一種處理同余式55x≡1（mod 3）的方法，就是當模不是太大的時候，可以把小于模3的3個整數0，1，2分別代入同余式試一下，看誰滿足，所以可以推出x≡1（mod 3），所以除數3對應的乘率是1.再看下一個3×11=33，33x≡1（mod 5），把33除以5，商6余3，所以33x≡1（mod 5），就變成了3x≡1（mod 5），模5不是很大可把小于模5的整數0，1，2，3，4這5個整數分別代入，容易得出x≡2（mod 5），除此之外還有一種處理方式，就是想辦法把x的系數變成1，通過把x的系數變到和模5越來越接近，比如5和4，6很接近，比如3x≡1（mod 5），兩邊乘上2，6x≡2（mod 5），又6≡1（mod 5），所以6x≡x（mod 5）x≡2（mod 5），所以除數5對應的乘率是2，在解同余式的過程中根據具體題目多種方法融入使用更加簡便.同樣地，3×5=15，15x≡1（mod 11），15≡4（mod 11），得4x≡1（mod 11），兩邊同乘3，12x≡3（mod 11），12≡1（mod 11），所以x≡3（mod 11），除數11對應的乘率是3.然后是各總，各總是什么呢？各總就是衍數、乘率、余數的乘積，55×1×1=55，33×2×（-2）=-132，15×3×4=180，答數就是55+（-132）+180=103，也就是各總之和，那么這個答數可能會比較大，而且大于最小公倍數，要求它是最小的正整數，則這個最小答數就是用答數除以最小公倍數求余數，或答數減去最小公倍數的倍數.算出最小答數代回同余式組驗證一下是否滿足，如果在驗證的過程中不滿足某一個，說明該行可能算錯了，經檢驗103是最小答數，這是孫子定理的算法.對于同余式組來說，要求出所有的解，也是很容易的，剛才在求最小答數的時候是減去最小公倍數的若干倍，現在是加上165的若干倍，所有解x≡103+165k，k∈Z.

解 ∵ 3，5，11兩兩互質，由孫子定理得

m=3×5×11=165，

M1=5×11，5×11×M′1≡1（mod 3），M′1=1，

M2=3×11，3×11×M′2≡1（mod 5），M′2=2，

M3=3×5，3×5×M′3≡1（mod 11），M′3=3，

∴x≡5×11×1×1+3×11×2×（-2）+3×5×3×4（mod 165）

≡103（mod 165）.

例2 求解同余式組x≡5（mod 7），x≡3（mod 12），x≡17（mod 55）.

分析 要求這個同余式組，列表如下：

其中乘率，求660x≡1（mod 7）的解，（660，7）=1，1|1有解，這個解怎么來求呢？實際上就是求660s+7t=1.來看怎么方便快捷地求出x，首先我們把660除以7，商94余2，所以660x≡1（mod 7）就變成了2x≡1（mod 7），為什么660可以寫成被7除的余數2呢？因為660≡2（mod 7），兩邊同乘x，660x≡2x（mod 7），要找660x≡1（mod 7），由同余的傳遞性，有2x≡1（mod 7）.所以由660x≡1（mod 7）就推出2x≡1（mod 7），那返回去怎么辦呢？返回去實際上也是一樣的，因為660x與2x同余，2x與1同余，由傳遞性，所以660x與1同余，因此660x≡1（mod 7）2x≡1（mod 7），然后從2x≡1（mod 7）里邊找x，怎么找呢？因為（2，7）=1，所以它只有1個解，現在我們要求2s+7t=1很容易.或當模不是太大的時候，我們也可以從0到6一個一個代進去試一下，看誰滿足，所以可以推出x=4，因此除數7對應的乘率是4.在這里還有一種解法，就是想辦法把x的系數變成1，通過把x的系數變到和7越來越接近，比如6和8與7很接近，比如在2x≡1（mod 7）兩邊乘上3，得6x≡3（mod 7），因6模7余-1，所以-x≡3（mod 7），兩邊乘-1，x≡-3（mod 7），-3被7除，因-3=-1×7+4，找最小正整數，就是4，所以x=4，或者在式子2x≡1（mod 7）兩邊乘4，得8x≡4（mod 7），又8模7余1，x≡4（mod 7），所以得到的也是4，這是乘率.這個除數和余數根據同余式組可以直接寫出來，最小公倍數的計算也簡單.衍數呢？在除數里邊，除了這一行所在的數，把其他幾個除數乘起來便可.乘率稍稍麻煩一點，要把它們解出來，對于模7，4是第一個乘率.對于模12的乘率，就是要找385x≡1（mod 12）的解，現在我們還是按剛才的辦法，385太大，把它變小，就是385被12除找余數，385除以12，商32余1，原同余式等價于x≡1（mod 12），所以12對應的乘率為1，最后一個乘率，找84x≡1（mod 55）的解，當然我們還是用84被55除，來看它的余數，29x≡1（mod 55），下面我們再讓它接近55，然后再去掉55的倍數，上式兩邊乘2，得58x≡2（mod 55），再模一個55，得3x≡2（mod 55），再讓3與55接近，式子兩邊同時乘18，54x≡36（mod 55），又54=1×55-1，54模55余-1，有-x≡36（mod 55），式子兩邊乘-1，x≡-36（mod 55），取最小正整數19，當然也不一定找最小的正整數，只是為了和古代的孫子算經對應，里面找的就是最小正整數.下面就要算各總，各總就是將表格每一行里邊的衍數、乘率、余數這3個數乘起來，它們依次為660×4×5=13200，385×1×3=1155，84×19×17=27132，答數就是把各數加起來得41487，最小答數就是用答數除以最小公倍數，求余數，41487÷4620=8……4527，最小答數為4527.

算出最小答數代回同余式組驗證一下是否滿足，如果在驗證的過程中不滿足某一個，說明該行可能算錯了.經檢驗4527是最小答數，這就是孫子算經的算法.對于同余式組來說，要求出所有的解也是很容易的，所有的解為x=4527+4620k.我們在求最小答數的時候是去掉4620的若干倍，而所有的解是加上4620的若干倍.

4 結論

中國著名數學著作《孫子算經》中記載“物不知數”問題，就是孫子定理的體現，給出了求解一般同余式組的方法，成為解決特定一次同余式組的主要模式.文章對孫子定理進行了闡述，并通過實例對孫子定理問題的算法進行了詳細的分析.但孫子定理也有一定缺陷，求解同余式、同余式組并不完善，有一定的局限性，要求模必須兩兩互素，且解法唯一.文章僅分析了一些簡單的例子，以幫助學者更好地理解并掌握算法，相關問題有待進一步探討.

【參考文獻】

[1]潘承洞，潘承彪.初等數論（第二版）[M].北京：北京大學出版社，2003.

[2]閔嗣鶴，嚴士健.初等數論（第三版）[M].北京：高等教育出版社，2003.

[3]課程教材研究所，數學課程教材研究開發中心.初等數論 [M].北京：人民教育出版社，2006.

[4]胡典順，徐漢文.初等數論（第二版）[M].科學出版社，2017.

[5]邊紅平.初等數論[M].浙江大學出版社，2007.

[6] 柯召，孫琦.數論講義（第二版）[M].北京：高等教育出版社，2001.