同余（九）——孙子定理（中国剩余定理）

往期文章

同余（一）

同余（二）

同余（三）

同余（四）—书籍书号的小秘密

同余（五）——费马小定理

同余（六）——斐波那契数列

同余（七）——密码学中的应用

同余（八）——欧拉定理

整数与整除问题  

导读

   孙子定理是中国古代求解一次同余式组的方法。是数论中四大定理之一。又称中国剩余定理。

   在数学著作《孙子算经》中，提到一个“物不知数”问题，原文如下：

   有物不知其数，三三数之剩二，五五数之剩三，七七数之剩二。问物几何？

孙子算经

      《孙子算经》的作者生平和编写年不详，一般认为是东晋时期的作品，比孙武的《孙子兵法》要晚很多。用我们现在学习的数学语言来描述“物不知数”问题：

       算经中给出答案是23，23是满足同余方程组的最小正整数。并给出了上述问题的一般解法。

       宋代数学家秦九韶在其名著《数书九章》中考虑了更一般化同余方程组的解法。

最终他得到了下面的定理。

孙子定理

定理  假设整数m₁,m₂, ... ,m_n两两互质，则对任意的整数：a₁,a₂, ... ,a_n,上述同余方程组有唯一解。

其中

            

         

      

证明  

     从假设可知，（m_i,M_i）=1，故存在整数

使得

             

另一方面，对i≠j , m_j|M_i, 因此

所以

      

满足

     又若x₁,x₂,是方程组的两个解，则

            x₁≡x₂（mod m_i） 1≤i≤n

考虑到（m_i,m_j）=1(i≠j), 即可知

              x₁≡x₂（mod m）  

所以解是唯一的。

                                                    □

定理应用

例子1（韩信点兵）

      有兵一队，若列成5行纵队，则末行1人；成6行纵队，则末行5人；成7行纵队，则末行4人；成11行纵队，则末行10人，求兵数？

 解    此时m=5×6×7×11=2310

            M₁=462，M₂=385，

             M₃=330，M₄=210.

        解

        得到

             t₁=3，t₂=t₃=t₄=1,,

        在根据定理得到

               x≡2111（mod 2310）.

  注：这个例子说明，在秦朝末年时期，就有了孙子定理的特例。

定理故事

      孙子定理是中国古代数学史上最值得骄傲的结论，国内外每一本数论书中都有此定理。它在抽象代数中也有其相应的推广，同时它也被应用到密码学的理论中。

       严格来说，孙子定理应称为孙子—秦九韶定理或秦九韶定理。