孫子定理的發(fā)展應(yīng)用

張藝林

摘要：孫子定理又稱中國(guó)剩余定理，是數(shù)論中非常重要的定理，是學(xué)習(xí)數(shù)論和近世代數(shù)的基礎(chǔ)。據(jù)此，論述了孫子定理的發(fā)展及其在賦值理論和密碼學(xué)等方面的應(yīng)用，給出了簡(jiǎn)單的證明。

關(guān)鍵詞：中國(guó)剩余定理；發(fā)展；應(yīng)用

中圖分類號(hào)：G4

文獻(xiàn)標(biāo)識(shí)碼：A

doi：10.19311/j.cnki.16723198.2017.30.074

孫子定理又被稱為中國(guó)剩余定理，是數(shù)論中的重要定理，在中國(guó)數(shù)學(xué)史上具有相當(dāng)高的地位。孫子定理給出了求解同余方程的一般方法，剩余問題在數(shù)論和近世代數(shù)中都有廣泛的應(yīng)用。

1孫子定理的發(fā)展

我國(guó)古代就流傳著許多傳說，譬如“隔墻算”、“剪管術(shù)”、“物不知其數(shù)”、“韓信點(diǎn)兵”、“鬼谷算”等。古代人民口口相傳中的這些傳說在現(xiàn)在看來就是一些趣味十足的數(shù)字游戲，它們的文字描述不盡相同，但所表達(dá)的數(shù)學(xué)意義是一致的，它們從不同的方面為我們列舉出了 “剩余問題”的解法。這在我國(guó)古代的數(shù)學(xué)史上的影響非常大，孫子定理在密碼學(xué)、多項(xiàng)式、賦值理論等方面也被廣泛應(yīng)用。《孫子算經(jīng)》是最早記錄這類算法的書，十三世紀(jì)后期，數(shù)學(xué)家秦九韶在這方面取得了重大突破，他發(fā)現(xiàn)了一種新的算法，命名為“大衍求一術(shù)”。

古代流傳著一首歌訣：“今有物，不知其數(shù)，三三數(shù)之，剩二；五五數(shù)之，剩三；七七數(shù)之，剩二”。問物幾何？歌訣的意思是：有批物品，三個(gè)為一組的數(shù)，剩余兩個(gè)；五個(gè)為一組的數(shù)，剩余三個(gè)；七個(gè)為一組的數(shù)，剩余兩個(gè)。問這批物品有多少？ 我們將這首歌訣稱為“物不知數(shù)”問題。

明代數(shù)學(xué)家程大位在《算法統(tǒng)宗》中如此描述：“三人同行七十稀，五樹梅花廿一，七子團(tuán)圓月正半，除百零五便得知”。意為：把用3除所得的余數(shù)乘以

70，加上用5除所得的余數(shù)乘以21，再加上用7除所得的余數(shù)乘以15，如果所得的數(shù)大于105， 就減去105的倍數(shù)，即得所求的數(shù)。

用數(shù)學(xué)表達(dá)式解釋為：2×7+3×21+2×15=233，233-105×2=23。這是早期給出的同余方程組的解法。

下面介紹孫子定理的內(nèi)容。

3孫子定理的應(yīng)用

3.1余同加余

一個(gè)數(shù)除以不同的數(shù)得到了一樣的余數(shù)。我們就能夠知道這個(gè)數(shù)等于這幾個(gè)除數(shù)的最小公倍數(shù)的整倍數(shù)加上它們一樣的余數(shù)。這種方法被稱為余同加余。

例3三位的自然數(shù)，用它除以6余3，除以5余3，除以4余3。則滿足條件的自然數(shù)有幾個(gè)？

分析 此題可用孫子定理給出的解法來求解。

解4、5、6的最小公倍數(shù)是60，能夠得到N=60n+3，已知N是個(gè)三位數(shù)，這里的n是整數(shù)。即n的取值范圍為2到16，因此能夠取得的數(shù)共有15個(gè)。

3.2合同加和

一個(gè)數(shù)除以不同的數(shù)得到的余數(shù)不同，但每個(gè)式子中的除數(shù)與余數(shù)之和相同，那么這個(gè)數(shù)即為除數(shù)的最小公倍數(shù)的整數(shù)倍加上余數(shù)與除數(shù)之和。這種方法稱為和同加和。

例4新學(xué)期即將來臨，學(xué)校需要為新生安排宿舍，高一年級(jí)共有女生若干人，如果將女生全部安排住進(jìn)七人間，則會(huì)剩下兩個(gè)人住在一個(gè)宿舍里；如果將這女生全部安排住進(jìn)六人間，則會(huì)剩下三個(gè)人住在一個(gè)宿舍里；如果將女生全部安排住進(jìn)五人間，則會(huì)剩下四個(gè)人住在一個(gè)宿舍里。試問這個(gè)年級(jí)總共有多少名女生？

分析從題中我們可以獲得的信息有：余數(shù)與除數(shù)的和一樣都是9，采取和同加和原理。

解7、5、6的最小公倍數(shù)是210，我們可以總結(jié)出的表達(dá)式為210n+9，通過計(jì)算可以得知本年級(jí)的女生人數(shù)為219人。

3.3差同減差

一個(gè)數(shù)除以不同的數(shù)得到的余數(shù)不同，但是每個(gè)式子中除數(shù)減去余數(shù)的差相同每個(gè)式子除數(shù)減余數(shù)的差相同，那么這個(gè)數(shù)即為除數(shù)的最小公倍數(shù)的整數(shù)倍再減去除數(shù)與余數(shù)之差。這種方法稱為差同減差。

例5某語文老師讓學(xué)生寫生字，生字總量在一百到一百五之間，小明按照每行寫四個(gè)生字，最后一行只寫了三個(gè)生字。小紅按照每行寫五個(gè)生字，最后一行只寫了四個(gè)生字。小王按照每行寫六個(gè)生字，最后一行只寫了五個(gè)生字。試求老師總共布置了多少個(gè)生字？

分析通過讀題我們能夠得到下面這些信息：每位學(xué)生最后一行與前面每一行只相差一個(gè)單詞，能夠直接用差同減差。

解4，、5、6的最小公倍數(shù)是120，生字總數(shù)就可以表示為120n-1，題目限定生字總量在一百到一百五之間，可知老師總共布置了119個(gè)生字。

在上面的三類問題中都涉及了孫子定理的數(shù)學(xué)思想。

3.4孫子定理的密碼學(xué)方面的應(yīng)用

隨著社會(huì)經(jīng)濟(jì)的發(fā)展和計(jì)算機(jī)網(wǎng)絡(luò)的普及，人們的生活更加依賴于數(shù)字化的信息技術(shù)，依賴于為信息安全提供保障的密碼學(xué)。孫子定理是數(shù)論中的一個(gè)基本定理，在現(xiàn)代密碼學(xué)的研究中有著重要的作用，在公鑰加密、秘密共享、數(shù)字簽名等領(lǐng)域都有著重要應(yīng)用。

參考文獻(xiàn)

[1]李文林.數(shù)學(xué)史教程[M].北京：高等教育出版社，2004.

[2]陳景潤(rùn).初等數(shù)論[M].北京：科學(xué)出版社，1978.

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

[4]華羅庚.數(shù)論導(dǎo)引[M].北京：科學(xué)出版社，1995.

[5]李文林.袁向東.論漢歷上元積年的計(jì)算.科技史文集[M].上海：上?？茖W(xué)技術(shù)出版社，1982：7075.

[6]李懋.中國(guó)剩余定理及其應(yīng)用[J].西南師范大學(xué)學(xué)報(bào).自然科學(xué)版，2012.endprint