趙云平

【摘要】孫子定理在各版本的初等數(shù)論教材中均有介紹，但細(xì)節(jié)不夠明確，使讀者在學(xué)習(xí)過(guò)程中產(chǎn)生很多疑問(wèn)，本文在給出孫子定理的基礎(chǔ)上，通過(guò)實(shí)例詳細(xì)分析了孫子定理的算法，讓更多的讀者受益.

【關(guān)鍵詞】孫子定理;同余式;一次同余式組

孫子定理在數(shù)論及近世代數(shù)學(xué)領(lǐng)域是非常重要的理論，起著基礎(chǔ)作用，所解決的問(wèn)題是求未知量的系數(shù)為1，模兩兩互質(zhì)的一次同余式的解.它在國(guó)際上被稱為中國(guó)剩余定理或中國(guó)余數(shù)定理，是數(shù)論中一個(gè)重要定理，定理的構(gòu)造值得仔細(xì)推敲.求解一個(gè)未知數(shù)聯(lián)立同余式組，通常應(yīng)用“孫子定理”，這是初等數(shù)論教材中介紹的主要算法.

1 基本概念

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

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

定理1[2] 一次同余式ax≡b（mod m），當(dāng)（a，m）=1時(shí)，有唯一解.

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

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

2 孫子定理

定理4（孫子定理）[1-6] 設(shè)m1，m2，…，mk是k個(gè)兩兩互質(zhì)的正整數(shù)，

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.列表如下：

這個(gè)孫子定理就給出了求解一次同余式組的一般算法，這是關(guān)于模m的運(yùn)算.

3 具體算法與實(shí)例

這個(gè)方法具體是什么呢？來(lái)看幾個(gè)例子.

例1 求解同余式組

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

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

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

解 ∵ 3，5，11兩兩互質(zhì)，由孫子定理得

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）.

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

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

算出最小答數(shù)代回同余式組驗(yàn)證一下是否滿足，如果在驗(yàn)證的過(guò)程中不滿足某一個(gè)，說(shuō)明該行可能算錯(cuò)了.經(jīng)檢驗(yàn)4527是最小答數(shù)，這就是孫子算經(jīng)的算法.對(duì)于同余式組來(lái)說(shuō)，要求出所有的解也是很容易的，所有的解為x=4527+4620k.我們?cè)谇笞钚〈饠?shù)的時(shí)候是去掉4620的若干倍，而所有的解是加上4620的若干倍.

4 結(jié)論

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

【參考文獻(xiàn)】

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

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

[3]課程教材研究所，數(shù)學(xué)課程教材研究開(kāi)發(fā)中心.初等數(shù)論 [M].北京：人民教育出版社，2006.

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

[5]邊紅平.初等數(shù)論[M].浙江大學(xué)出版社，2007.

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