孫子定理(中國剩餘定理)

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

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

基本介紹

• 中文名：孫子定理
• 外文名：Chinese remainder theorem(CRT)
• 分類：數學 
• 提出：孫子
• 問題：一元線性同餘方程組
• 又名：餘數定理

公式

用現代數學的語言來說明的話，中國剩餘定理給出了以下的一元線性同餘方程組：

有解的判定條件，並用構造法給出了在有解情況下解的具體形式。

中國剩餘定理說明：假設整數m₁,m₂, ... ,m_n兩兩互質，則對任意的整數：a₁,a₂, ... ,a_n，方程組 有解，並且通解可以用如下方式構造得到：

設 是整數m₁,m₂, ... ,m_n的乘積，並設 是除了m_i以外的n- 1個整數的乘積。

設 為 模 的數論倒數( 為 模 意義下的逆元)

方程組 的通解形式為

在模 的意義下，方程組 只有一個解：

證明：

從假設可知，對任何 ，由於 ，所以 這說明存在整數 使得 這樣的 叫做 模 的數論倒數。考察乘積 可知：

所以 滿足：

這說明 就是方程組 的一個解。

另外，假設 和 都是方程組 的解，那么：

而 兩兩互質，這說明 整除 . 所以方程組 的任何兩個解之間必然相差 的整數倍。而另一方面， 是一個解，同時所有形式為：

的整數也是方程組 的解。所以方程組所有的解的集合就是：

文獻

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

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

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

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

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

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

交換環上推廣

主理想整環

設R是一個主理想整環，m₁, m₂, ... , m_k是其中的k個元素，並且兩兩互質。令M m₁m₂...m_n為這些元素的乘積，那么可以定義一個從商環R/MR映射到環乘積R/m₁R × … × R/m_kR的同態：

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

而映射

就是 的逆映射。

也是一個主理想整環。將以上的R換成 ，就能得到中國剩餘定理。因為

一般的交換環

設R是一個有單位元的交換環，I₁,I₂, ... ,I_k是為環 的理想，並且當 時 ，，則有典範的環同構：

數論相關

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

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

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

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

例題解析

例一：一個數，除以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