孫子定理

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

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

中國剩餘定理説明：假設整數m₁,m₂, ... ,m_n兩兩互質，則對任意的整數：a₁,a₂, ... ,a_n，方程組

有解，並且通解可以用如下方式構造得到：

設

是整數m₁,m₂, ... ,m_n的乘積，並設

是除了m_i以外的n- 1個整數的乘積。

設

為

模

的數論倒數(

為

模

意義下的逆元)

方程組

的通解形式為

在模

的意義下，方程組

只有一個解：

證明 ^[1]  ：

從假設可知，對任何

，由於

，所以

這説明存在整數

使得

這樣的

叫做

模

的數論倒數。考察乘積

可知：

所以

滿足：

這説明

就是方程組

的一個解。

另外，假設

和

都是方程組

的解，那麼：

而

兩兩互質，這説明

整除

. 所以方程組

的任何兩個解之間必然相差

的整數倍。而另一方面，

是一個解，同時所有形式為：

的整數也是方程組

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

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

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

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

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

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

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

在西方，與《孫子算經》同類的算法，最早見於1202年意大利數學家斐波那契的《算經》。1801年，德國數學家高斯的《算術探究》中，才明確寫出了這一問題的求法。 ^[3] 

設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的數從小到大排列：1，6，11，16，21，26，……

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

所以11就是所求的數。

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

特殊的方法：最小公倍法

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

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

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

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

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

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

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

多個數的，比如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除餘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

題目可以看成，除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