Sunzi shengyu dingli
孙子剩余定理


   中国南北朝时期（5～6世纪）著名的著作《孙子算经》中“物不知数”问题所阐述的定理。物不知数问题的原题是：“今有物，不知其数，三三数之剩二，五五数之剩三，七七数之剩二，问物几何？”这属于数论的一次同余方程组问题。用现代数学符号可表为求下列同余方程的整数解：
                  [649-06]式中[649-07]
　《孙子算经》中使用一种适合解一般的一次同余方程组的方法，求得此特殊问题的最小整数解=23。解题步骤是：选定5×7的一个倍数，被3除余1，即70；选定3×7的一个倍数，被5除余1，即21；选定3×5的一个倍数，被7除余1，即15。然后按下式计算
          [649-08]式中105为3,5,7的最小公倍数，为适当选取的整数,使得0＜ ≤105，这里取=2。
　上述问题和解法，可直接推广为定理：设1,2,…,两两互素，[649-09]则
           [649-10],        (1)有整数解,且对模是惟一的若记最小正整数解为,则
               [649-11],式中满足
          [649-12]。为适当选取的整数,使得≤“物不知数”问题,[2kg]在欧洲是一个知名的问题，C.F.高斯于19世纪初给出了它的一般性定理。因此国际上称上述《孙子算经》中的问题为孙子剩余定理或中国剩余定理。
　《孙子算经》没有给出求的具体算法。宋代秦九韶在《数书九章》中第一次详细地、完整地阐述了求解一次同余方程组的算法，他称做“大衍总数术”，其中包括求的一种机械化算法──大衍求一术。
　秦九韶称为“定数”，为“乘率”,由[649-13]中屡减所得的余数(<)为“奇数”。“大衍求一术云：置奇右上，定居右下,立天元一于左上(图1[])。先以右上除右下，所得商数与左上一相生(即相乘)入左下。然后乃以右行上下以少除多，递互除之，所得商数随即递互累乘归左行上下，须使右上末后奇一而止。乃验左上所得，以为乘率。”秦九韶在例题中曾以=3,=4为例，列出求的算草布式：
       [649-15]
        [649-16]此时右上余1，故左上即为乘率=3。
　秦九韶还在历史上首次提出了当 1,2,…,并非两两互素时, 求解(1)的方法他设计了“两两连环求等,约奇弗约偶”，“复乘求定”等算法,先约去诸模数1,2,…,中包含的多余的因子,得到新的一组[650-111],使 [650-1]恰为 1,2,…,的最小公倍数。再对[650-111],中的因子重新归并，得到[650-02]使[650-222]仍为1,2,…,的最小公倍数，且它们两两互素。这样便将问题化约为模数两两互素的情形。秦九韶尚未提及当1,2,…,并非两两互素时，方程(1)可解的条件。但从他所举八道例题中有七道的模数满足可解条件这一事实分析，许多人认为秦九韶已知道该条件。
　　　　　　　　　　　　　袁向东　李文林