crt （中国剩余定理）

简介

有物不知其数，三三数之剩二，五五数之剩三，七七数之剩二。问物几何？即，一个整数除以三余二，除以五余三，除以七余二，求这个整数的值。《孙子算经》中首次提到了同余方程组的问题，以及以上具体问题的解法，因此在中文数学文献中也会将中国剩余定理称为孙子定理。

简介

用现代数学的语言来说明的话，中国剩余定理给出了以下的一元线性同余方程组：

有解的判定条件，并用构造法给出了在有解情况下解的具体形式。

中国剩余定理说明：假设整数

设

设

方程组

在模

证明：

从假设可知，对任何

所以

这说明

另外，假设

而

的整数也是方程组

文献

一元线性同余方程组问题最早可见于中国南北朝时期（公元5世纪）的数学著作《孙子算经》卷下第二十六题，叫做“物不知数”问题，原文如下：

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

即，一个整数除以三余二，除以五余三，除以七余二，求这个整数。《孙子算经》中首次提到了同余方程组问题，以及以上具体问题的解法，因此在中文数学文献中也会将中国剩余定理称为孙子定理。

宋朝数学家秦九韶于1247年《数书九章》卷一、二《大衍类》对“物不知数”问题做出了完整系统的解答。明朝数学家程大位将解法编成易于上口的《孙子歌诀》：

三人同行七十稀，五树梅花廿一支，七子团圆正半月，除百零五使得知

这个歌诀给出了模数为3、5、7时候的同余方程的秦九韶解法。意思是：将除以3得到的余数乘以70，将除以5得到的余数乘以21，将除以7得到的余数乘以15，全部加起来后减去105（或者105的倍数），得到的余数就是答案。比如说在以上的物不知数问题里面，按歌诀求出的结果就是23。

交换环上推广

主理想整环

设R是一个主理想整环，

并且

而映射

就是

一般的交换环

设R是一个有单位元的交换环，

数论相关

数论是纯粹数学的分支之一，主要研究整数的性质。

按研究方法来看，数论大致可分为初等数论和高等数论。初等数论是用初等方法研究的数论，它的研究方法本质上说，就是利用整数环的整除性质，主要包括整除理论、同余理论、连分数理论。高等数论则包括了更为深刻的数学研究工具。它大致包括代数数论、解析数论、计算数论等等。

初等数论主要就是研究整数环的整除理论及同余理论。此外它也包括了连分数理论和少许不定方程的问题。本质上说，初等数论的研究手段局限在整除性质上。

初等数论中经典的结论包括算术基本定理、欧几里得的质数无限证明、中国剩余定理、欧拉定理（其特例是费马小定理）、高斯的二次互反律，勾股方程的商高定理、佩尔方程的连分数求解法等等。

例题解析

例一：一个数，除以5余1，除以3余2。问这个数最小是多少？

采用通用的方法：逐步满足法

把除以5余1的数从小到大排列：1，6，11，16，21，26，……

然后从小到大找除以3余2的，发现最小的是11.

所以11就是所求的数。

先满足一个条件，再满足另一个条件，所以称之为“逐步满足法”。

例二：一个数除以5余1，除以3也余1。问这个数最小是多少？（1除外）

特殊的方法：最小公倍法

除以5余1：说明这个数减去1后是5的倍数。

除以3余1：说明这个数减去1后也是3的倍数。

所以，这个数减去1后是3和5的公倍数。要求最小，所以这个数减去1后就是3和5的最小公倍数。即这个数减去1后是15，所以这个数是

例三：一个数除以5余4，除以3余2。问这个数最小是多少？

这种情况也可以用最小公倍法。

数除以5余4，说明这个数加上1后是5的倍数。

数除以3余2，说明这个数加上1后也是3的倍数。

所以，这个数加上1后是3和5的公倍数。要求最小，所以这个数加上1后就是3和5的最小公倍数。即这个数加上1后是15，所以这个数是

多个数的，比如3个数的，有时候其中两个可以用特殊法，那就先用特殊法，用特殊法求出满足两个条件的数后再用通用的方法求满足最后一个条件的数。

例四：有1个数，除以7余2．除以8余4，除以9余3，这个数至少是多少？

除以7余2的数可以写成

7n除以8余2，7除以8余7，要求n除以8余6（乘数之余等于余数之乘），则n最小取6。

所以满足“除以7余2，除以8余4”的最小的数是

所有满足“除以7余2，除以8余4”的数都可以写成

要求

所以满足“除以7余2，除以8余4，除以9余3”的最小的数是

例五：三三数之剩二，五五数之剩三，七七数之剩二。问物几何？

即，一个整数除以三余二，除以五余三，除以七余二，求这个整数。

除以3余2和除以7余2的数可以写成

21n除以5余1，21除以5余1，要求n除以5余1（乘数之余等于余数之乘），则n最小取1。

所以满足“除以3余2，除以5余3，除以7余2”的最小的数是

标准解法：先从3和5、3和7、5和7的公倍数中相应地找出分别被7、5、3除均余1的较小数15、21、70(注释：此步又称为求"模逆"运算，利用扩展欧几里得法并借助计算机编程可比较快速地求得。当然，对于很小的数，可以直接死算)。即

再用找到的三个较小数分别乘以所要求的数被7、5、3除所得的余数的积连加，

最后用和233除以3、5、7三个除数的最小公倍数.

这个余数23就是合乎条件的最小数.

例六：一个数被5除余2，被6除少2，被7除少3，这个数最小是多少?

题目可以看成，被5除余2，被6除余4，被7除余4。看到那个“被6除余4，被7除余4”了么，有同余数的话，只要求出6和7的最小公倍数，再加上4，就是满足后面条件的数了，

下面一步试下46能不能满足第一个条件“一个数被5除余2”。不行的话，只要再46加上6和7的最小公倍数42，一直加到能满足“一个数被5除余2”。这步的原因是，42是6和7的最小公倍数，再怎么加都会满足“被6除余4，被7除余4”的条件。

例7：一个班学生分组做游戏，如果每组三人就多两人，每组五人就多三人，每组七人就多四人，问这个班有多少学生?

题目可以看成，除3余2，除5余3，除7余4。没有同余的情况，用的方法是“逐步约束法”，就是从“除7余4的数”中找出符合“除5余3的数”，就是再7上一直加7，直到所得的数除5余3。得出数为18，下面只要在18上一直加7和5得最小公倍数35，直到满足“除3余2”