中國剩餘定理

中國剩餘定理

圖片來自搜狐網

中國剩餘定理，孫子定理是中國古代求解一次同餘式組（見同餘）的方法。是數論中一個重要定理。又稱中國餘數定理。一元線性同餘方程組問題最早可見於中國南北朝時期（公元5世紀）的數學著作《孫子算經》卷下第二十六題，叫做「物不知數」問題，原文如下：

有物不知其數，三三數之剩二，五五數之剩三，七七數之剩二。問物幾何？即，一個整數除以三餘二，除以五餘三，除以七餘二，求這個整數。《孫子算經》中首次提到了同餘方程組問題，以及以上具體問題的解法，因此在中文數學文獻中也會將中國剩餘定理稱為孫子定理。

目錄

孫子算經

《孫子算經》是中國古代重要的數學著作，共三卷，成書約在四、五世紀，作者生平和具體編寫年不詳。

其卷下的第26題為：

今有物不知其數，三三數之剩二，五五數之剩三，七七數之剩二，問物幾何？

答曰：『二十三』。

術曰：三三數之剩二，置一百四十；五五數之剩三，置六十三，七七數之剩二，置三十，並之。得二百三十三，以二百一十減之，即得。凡三三數之剩一，則置七十；五五數之剩一，則置二十一；七七數之剩一，則置十五；一百六以上以一百五減之即得。

（即—一個整數除以3餘2、除以5餘3、除以7餘2，求這個整數。

答案：23

解法：由於除以3餘2，因此加上一個140；由於除以5餘3，因此加上一個63；由於除以7餘2，因此加上一個30；這三個數的和是140+63+30=233，再減去210，就得到了23了。

這麼說吧，只要是除以3餘了一個1，就加上一個70；只要是除以5餘了一個1，就加上一個21；只要是除以7餘了一個1，就加上一個15。然後累加。超過了106就減去105就行了。該問題稱之為「物不知數」問題。

文獻

一元線性同餘方程組問題最早可見於中國南北朝時期（公元5世紀）的數學著作《孫子算經》卷下第二十六題，叫做「物不知數」問題，原文如下：

有物不知其數，三三數之剩二，五五數之剩三，七七數之剩二。問物幾何？

即，一個整數除以三餘二，除以五餘三，除以七餘二，求這個整數。《孫子算經》中首次提到了同餘方程組問題，以及以上具體問題的解法，因此在中文數學文獻中也會將中國剩餘定理稱為孫子定理。

宋朝數學家秦九韶於1247年《數書九章》卷一、二《大衍類》對「物不知數」問題做出了完整系統的解答。明朝數學家程大位將解法編成易於上口的《孫子歌訣》：

三人同行七十稀，五樹梅花廿一支，七子團圓正半月，除百零五使得知

這個歌訣給出了模數為3、5、7時候的同餘方程的秦九韶解法。意思是：將除以3得到的餘數乘以70，將除以5得到的餘數乘以21，將除以7得到的餘數乘以15，全部加起來後除以105（或者105的倍數），得到的餘數就是答案。比如說在以上的物不知數問題裡面，按歌訣求出的結果就是23。

設R是一個主理想整環，m1, m2, ... , mk是其中的k個元素，並且兩兩互質。令M

m1m2...mn為這些元素的乘積，那麼可以定義一個從商環R/MR映射到環乘積R/m1R × … × R/mkR的同態：

並且 的逆映射也存在。而這個逆映射的構造方式就如同中國剩餘定理構造一元線性同餘方程組的解一樣。由於mi和Mi=M/mi互質，所以存在si和ti使得而映射就是的逆映射。

一般的交換環

設R是一個有單位元的交換環，I1,I2, ... ,Ik是為環

數論相關

數論是純粹數學的分支之一，主要研究整數的性質。

按研究方法來看，數論大致可分為初等數論和高等數論。初等數論是用初等方法研究的數論，它的研究方法本質上說，就是利用整數環的整除性質，主要包括整除理論、同餘理論、連分數理論。高等數論則包括了更為深刻的數學研究工具。它大致包括代數數論、解析數論、計算數論等等。

初等數論主要就是研究整數環的整除理論及同餘理論。此外它也包括了連分數理論和少許不定方程的問題。本質上說，初等數論的研究手段局限在整除性質上。

初等數論中經典的結論包括算術基本定理、歐幾里得的質數無限證明、中國剩餘定理、歐拉定理（其特例是費馬小定理）、高斯的二次互反律， 勾股方程的商高定理、佩爾方程的連分數求解法等等。

例題解析

例一：一個數，除以5餘1，除以3餘2。問這個數最小是多少？

採用通用的方法：逐步滿足法

把除以5餘1的數從小到大排列：1，6，11，16，21，26，……

然後從小到大找除以3餘2的，發現最小的是11.

所以11就是所求的數。

先滿足一個條件，再滿足另一個條件，所以稱之為「逐步滿足法」。

例二：一個數除以5餘1，除以3也餘1。問這個數最小是多少？（1除外）

特殊的方法：最小公倍法

除以5餘1：說明這個數減去1後是5的倍數。

除以3餘1：說明這個數減去1後也是3的倍數。

所以，這個數減去1後是3和5的公倍數。要求最小，所以這個數減去1後就是3和5的最小公倍數。即這個數減去1後是15，所以這個數是15+1=16.

例三：一個數除以5餘4，除以3餘2。問這個數最小是多少？

這種情況也可以用最小公倍法。

數除以5餘4，說明這個數加上1後是5的倍數。

數除以3餘2，說明這個數加上1後也是3的倍數。

所以，這個數加上1後是3和5的公倍數。要求最小，所以這個數加上1後就是3和5的最小公倍數。即這個數加上1後是15，所以這個數是15－1=14。

多個數的，比如3個數的，有時候其中兩個可以用特殊法，那就先用特殊法，用特殊法求出滿足兩個條件的數後再用通用的方法求滿足最後一個條件的數。

例四：有1個數，除以7餘2．除以8餘4，除以9餘3，這個數至少是多少？

除以7餘2的數可以寫成7n+2。

7n+2這樣的數除以8餘4，由於2除以8餘2，所以要求7n除以8餘2。

7n除以8餘2，7除以8餘7，要求n除以8餘6（乘數之餘等於餘數之乘），則n最小取6。

所以滿足「除以7餘2，除以8餘4」的最小的數是7×6+2=44，

所有滿足「除以7餘2，除以8餘4」的數都可以寫成44+56×m。

要求44+56×m除以9餘3，由於44除以9餘8，所以要求56×m除以9餘4。（加數之餘等於餘數之加）

56×m除以9餘4，由於56除以9餘2，所以要求m除以9餘2（乘數之餘等於餘數之乘），則m最小取2。

所以滿足「除以7餘2，除以8餘4，除以9餘3」的最小的數是44+56×2=156。

例五：三三數之剩二，五五數之剩三，七七數之剩二。問物幾何？

即，一個整數除以三餘二，除以五餘三，除以七餘二，求這個整數。

除以3餘2和除以7餘2的數可以寫成21n+2。

21n+2除以5餘3，要求21n除以5餘1。

21n除以5餘1，21除以5餘1，要求n除以5餘1（乘數之餘等於餘數之乘），則n最小取1。

所以滿足「除以3餘2，除以5餘3，除以7餘2」的最小的數是21×1+2=23。

標準解法：先從3和5、3和7、5和7的公倍數中相應地找出分別被7、5、3除均餘1的較小數15、21、70 ( 注釋:此步又稱為求"模逆"運算,利用擴展歐幾里得法並藉助計算機編程可比較快速地求得.當然,對於很小的數,可以直接死算 )。即

15÷7=2……餘1，

21÷5=4……餘1，

70÷3=23……餘1.

再用找到的三個較小數分別乘以所要求的數被7、5、3除所得的餘數的積連加，

15×2+21×3+70×2=233. (將233處用i代替，用程序可以求出)

最後用和233除以3、5、7三個除數的最小公倍數.

233÷105=2……餘23，

這個餘數23就是合乎條件的最小數.

例六：一個數被5除餘2，被6除少2，被7除少3，這個數最小是多少?

題目可以看成，被5除餘2，被6除餘4，被7除餘4 。看到那個「被6除餘4，被7除餘4」了麼，有同餘數的話，只要求出6和7的最小公倍數，再加上4，就是滿足後麵條件的數了，6X7+4=46。

下面一步試下46能不能滿足第一個條件「一個數被5除餘2」。不行的話，只要再46加上6和7的最小公倍數42，一直加到能滿足「一個數被5除餘2」。這步的原因是，42是6和7的最小公倍數，再怎麼加都會滿足「被6除餘4，被7除餘4」的條件。

46+42=88

46+42+42=130

46+42+42+42=172

例7：一個班學生分組做遊戲，如果每組三人就多兩人，每組五人就多三人，每組七人就多四人，問這個班有多少學生?

題目可以看成，除3餘2，除5餘3，除7餘4。沒有同餘的情況，用的方法是「逐步約束法」，就是從「除7餘4的數」中找出符合「除5餘3的數」，就是再7上一直加7，直到所得的數除5餘3。得出數為18，下面只要在18上一直加7和5得最小公倍數35，直到滿足「除3餘2」

4+7=11

11+7=18

18+35=53