孫子算法

孫子算法即剩餘定理，《孫子算經》一書在我國和世界上最早提出了剩餘定理。

約成書於公元4世紀的數學著作《孫子算經》，載有“物不知數”問題：“今有物不知其數，三三數之剩五，五五數之剩三，七七數之剩二，問物幾何？”意思是，有一批物件，不知道它的數目，3個3個地數最後剩2個，5個5個地數最後剩3個，7個7個地數最後剩2個，問這批物件一共是多少？顯然，這相當於求不定方程組：
N＝3x＋2，N＝5y＋3，N＝7Z＋2，它的正整數解N，或用現代數論符號表示，等價於解一次同餘組。可是，《孫子算經》沒有採取簡單的方法試算，而是指出了科學的剩餘計算方法：三三數之，取數70，與餘數二相乘；五五數之，取數21，與餘數三相乘；七七數之，取數15，與餘數二相乘。將諸乘積相加，然後減去105的倍數。列成算式就是：
N＝70×2＋21×3＋15×2－2×105，答案是N＝23。
孫子算法的關鍵，在於70、21、15這三個數的確定。明代《算法統宗》中的“孫子歌”（三人同行七十稀，五樹梅花廿一枝，七子團圓正半月，除百令五便得知。）中也暗指了這三個關鍵的數字。《孫子算經》雖然沒有說明這三個數的來歷，但其列出的式子完全符合現代數論中著名的剩餘定理的計算。
“物不知數”問題，後經南宋數學家秦九韶於公元17世紀中葉研究發展為“一次同餘式理論”，被世界數學界稱為“中國的剩餘定理”。而歐洲德國數學家高斯研究出同一定理時，已經是公元19世紀初的事情了。