孫子剩餘定理

　　中國南北朝時期（5～6世紀）著名的著作《孫子算經》中“物不知數”問題所闡述的定理。物不知數問題的原題是：“今有物，不知其數，三三數之剩二，五五數之剩三，七七數之剩二，問物幾何？”這屬於數論的一次同餘方程組問題。用現代數學符號可表為求下列同餘方程的整數解：

式中

　　《孫子算經》中使用一種適合解一般的一次同餘方程組的方法，求得此特殊問題的最小整數解 N=23。解題步驟是：選定5×7的一個倍數，被3除餘1，即70；選定3×7的一個倍數，被5除餘1，即21；選定3×5的一個倍數，被7除餘1，即15。然後按下式計算

式中105為3，5，7的最小公倍數， p為適當選取的整數，使得0＜ N≤105，這裡取 p=2。

　　上述問題和解法，可直接推廣為定理：設α₁，α₂，…，α_n兩兩互素，

則

， (1)

有整數解，且對模 M是惟一的。若記最小正整數解為 N，則

，

式中 k _j滿足

。

p為適當選取的整數，使得 N≤ M。“物不知數”問題，在歐洲是一個知名的問題，C.F.高斯於19世紀初給出瞭它的一般性定理。因此國際上稱上述《孫子算經》中的問題為孫子剩餘定理或中國剩餘定理。

　　《孫子算經》沒有給出求k_j的具體算法。宋代秦九韶在《數書九章》中第一次詳細地、完整地闡述瞭求解一次同餘方程組的算法，他稱做“大衍總數術”，其中包括求k_j的一種機械化算法──大衍求一術。

　　秦九韶稱α_j為“定數”，k_j為“乘率”，由

中屢減 α _j所得的餘數 G _j(＜ α _j)為“奇數”。“大衍求一術雲：置奇右上，定居右下，立天元一於左上(圖 1 )。先以右上除右下，所得商數與左上一相生(即相乘)入左下。然後乃以右行上下以少除多，遞互除之，所得商數隨即遞互累乘歸左行上下，須使右上末後奇一而止。乃驗左上所得，以為乘率。”秦九韶在例題中曾以 G _j=3， α _j=4為例，列出求 k _j的算草佈式：

\ n

此時右上餘1，故左上即為乘率 k _j=3。

　　秦九韶還在歷史上首次提出瞭當α₁，α₂，…，α_n並非兩兩互素時，求解(1)的方法。他設計瞭“兩兩連環求等，約奇弗約偶”，"復乘求定"等算法，先約去諸模數α₁，α₂，…，α_n中包含的多餘的因子，得到新的一組

，使 恰為 α ₁， α ₂，…， α _n的最小公倍數。再對 ，中的因子重新歸並，得到 使 仍為 α ₁， α ₂，…， α _n的最小公倍數，且它們兩兩互素。這樣便將問題化約為模數兩兩互素的情形。秦九韶尚未提及當 α ₁， α ₂，…， α _n並非兩兩互素時，方程(1)可解的條件。但從他所舉八道例題中有七道的模數滿足可解條件這一事實分析，許多人認為秦九韶已知道該條件。