孫子定理的發展應用

張藝林

摘要：孫子定理又稱中國剩余定理，是數論中非常重要的定理，是學習數論和近世代數的基礎。據此，論述了孫子定理的發展及其在賦值理論和密碼學等方面的應用，給出了簡單的證明。

關鍵詞：中國剩余定理；發展；應用

中圖分類號：G4

文獻標識碼：A

doi：10.19311/j.cnki.16723198.2017.30.074

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

1孫子定理的發展

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

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

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

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

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

下面介紹孫子定理的內容。

3孫子定理的應用

3.1余同加余

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

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

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

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

3.2合同加和

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

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

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

解7、5、6的最小公倍數是210，我們可以總結出的表達式為210n+9，通過計算可以得知本年級的女生人數為219人。

3.3差同減差

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

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

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

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

在上面的三類問題中都涉及了孫子定理的數學思想。

3.4孫子定理的密碼學方面的應用

隨著社會經濟的發展和計算機網絡的普及，人們的生活更加依賴于數字化的信息技術，依賴于為信息安全提供保障的密碼學。孫子定理是數論中的一個基本定理，在現代密碼學的研究中有著重要的作用，在公鑰加密、秘密共享、數字簽名等領域都有著重要應用。

參考文獻

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

[2]陳景潤.初等數論[M].北京：科學出版社，1978.

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

[4]華羅庚.數論導引[M].北京：科學出版社，1995.

[5]李文林.袁向東.論漢歷上元積年的計算.科技史文集[M].上海：上海科學技術出版社，1982：7075.

[6]李懋.中國剩余定理及其應用[J].西南師范大學學報.自然科學版，2012.endprint