1 韓信點兵問題
這個問題首先要從一個叫做「韓信點兵」的故事說起。
秦末時期，楚漢相爭，漢初三傑之一的韓信有一次帶1500名兵士打仗，戰死四五百人。為了統計剩餘士兵的個數，韓信令士兵3人一排，多出2人；5人一排，多出4人；7人一排，多出6人。韓信據此很快說出人數：1049人。漢軍本來就十分信服韓信大將軍，經此之後就更加相信韓信是「天神下凡，神機妙算"，於是士氣大振，鼓聲喧天，在接下來的戰役中漢軍步步緊逼，楚軍亂作一團，大敗而逃。韓信由此名揚天下，被後世譽為「兵仙「，「神帥」。
那麼韓信是如何快速算出士兵人數的呢？韓信點兵問題可以用現代數學語言描述如下：若士兵人數是，則有除以3餘2，除以5餘4，除以7餘6.
我們也可以用同餘式來表示這個問題：
我們發現，若將，則可以同時被3、5、7整除，即
所以一定是3、5、7的最小公倍數的整數倍，由於3、5、7兩兩互素，則
所以
即
其中是正整數，當時
這樣，韓信就計算出了剩餘士兵的人數。
2 孫子算經與物不知數問題
實際上，這類問題就是在求解初等數論中的同餘方程組。在數學史上韓信點兵問題也被稱為物不知數問題，最早記載於一千多年前的《孫子算經》中：
「今有物不知其數，三三數之剩二，五五數之剩三，七七數之剩二，問物幾何？
轉化為現代數學語言，即解整數滿足的同餘式
這個問題和上文所說的韓信點兵問題類似，但是，它不具備上一個問題那麼好的性質，因為無論使加上或減去一個數，都無法同時被3、5、7整除。那麼，這個問題該如何解決呢？
宋朝數學家秦九韶於1247年《數書九章》卷一、二《大衍類》對「物不知數」問題做出了完整系統的解答。明朝數學家程大位將解法編成易於上口的《孫子歌訣》：
「三人同行七十稀，五樹梅花廿一支（二十一），七子團圓正半月，除百零五使得知。
這首詩的意思是：將除以3得到的餘數乘以70，將除以5得到的餘數乘以21，將除以7得到的餘數乘以15，全部加起來後除以105得到的餘數就是答案。
根據這個算法，可得：
因此物不知數問題的最小正整數解即為，事實上，23確實滿足除以3餘2，除以5餘3，除以7餘2，這個問題的通解為
其中是自然數。
3 中國剩餘定理
對於這個問題，如果是一般情況，該如何處理呢？例如，有同餘式：
我們把這個問題分解成三個同餘式方程組
那麼初始問題就有最小正整數解
因此只要能找到滿足條件的即可。以為例，由同餘式可得，
因此
所以存在使得
因此
其中的存在性可以證明，因為有如下定理：
「若，則必然存在使得
對於這個定理的證明，可以考慮集合中的最小正整數，只要證明這個最小正整數就是1即可。
考慮其中最小的正整數，，只需證明且，由於互素，所以只能為1.
這件事可以用反證法證明：若不能整除，則必有
因此
因此餘數也可以表示成一個整數乘以加上另一個整數乘以的形式，又因為是小於的，這就和最開始的假設是最小的正整數相矛盾了，因此必有
因此存在性得證。
事實上這樣的不僅存在，而且也比較好尋找，其中70就是既能被5、7同時整除又能除以3餘1的最小正整數，所以，同理可得，，因此這類問題就有了通解：
原來上面的古詩中出現的70、21、15這三個數是這麼來的！
一般來講，給定個不同的素數，則同餘方程組
一定是有解的，求解這個問題只需構造基礎解系:
因此有
因為都是素數，因此的存在性是顯然的。
求解上述問題的過程與方法就稱為「中國剩餘定理」，又稱為「孫子定理」。
中國剩餘定理的傳播最早在1852年由英國來華傳教士偉烈亞力將《孫子算經》中「物不知數」問題的解法傳至歐洲。1874年，英國數學家馬西森指出此法符合1801年由高斯得出的關於同餘式解法的一般性定理，因而西方稱之為「中國剩餘定理」，成為了初等數論中非常重要的一個定理。
來源：大小吳的數學課堂
編輯：荔枝