关于孙子剩余定理介绍

[拼音]：Sunzi shengyu dingli

中国南北朝时期（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。

上述问题和解法，可直接推广为定理：设α1，α2，…，αn两两互素，则

， (1)

有整数解，且对模M是惟一的。若记最小正整数解为N，则

，

式中kj满足

。

p为适当选取的整数，使得N≤M。“物不知数”问题，在欧洲是一个知名的问题，C.F.高斯于19世纪初给出了它的一般性定理。因此国际上称上述《孙子算经》中的问题为孙子剩余定理或中国剩余定理。

《孙子算经》没有给出求kj的具体算法。宋代秦九韶在《数书九章》中第一次详细地、完整地阐述了求解一次同余方程组的算法，他称做“大衍总数术”，其中包括求kj的一种机械化算法──大衍求一术。

秦九韶称αj为“定数”，kj为“乘率”，由

中屡减αj所得的余数Gj(<αj)为“奇数”。“大衍求一术云：置奇右上，定居右下，立天元一于左上(图1

)。先以右上除右下，所得商数与左上一相生(即相乘)入左下。然后乃以右行上下以少除多，递互除之，所得商数随即递互累乘归左行上下，须使右上末后奇一而止。乃验左上所得，以为乘率。”秦九韶在例题中曾以Gj=3，αj=4为例，列出求kj的算草布式：

此时右上余1，故左上即为乘率kj=3。

秦九韶还在历史上首次提出了当 α1，α2，…，αn并非两两互素时， 求解(1)的方法。他设计了“两两连环求等，约奇弗约偶”，"复乘求定"等算法，先约去诸模数α1，α2，…，αn中包含的多余的因子，得到新的一组，使 恰为 α1，α2，…，αn的最小公倍数。再对，中的因子重新归并，得到使仍为α1，α2，…，αn的最小公倍数，且它们两两互素。这样便将问题化约为模数两两互素的情形。秦九韶尚未提及当α1，α2，…，αn并非两两互素时，方程(1)可解的条件。但从他所举八道例题中有七道的模数满足可解条件这一事实分析，许多人认为秦九韶已知道该条件。