数论四大定理之中国剩余定理

中国剩余定理

中国剩余定理又称孙子定理，是中国古代求解一次同余式组的通用方法。同余方程组问题最早可见于中国南北朝时期（公元5世纪）的数学著作《孙子算经》卷下第二十六题，叫做“物不知数”问题，原文如下：

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

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

整数$a$满足$a\div 3\cdots\cdots2$，$a\div 5\cdots\cdots3$，$a\div 7\cdots\cdots2$，求$a$。

《孙子算经》中首次提到了同余方程组问题，以及以上具体问题的解法，因此在中文数学文献中也会将中国剩余定理称为孙子定理。《孙子算经》中给出了如下解法，但并没有系统解决这个问题。

“三三数之剩二，置一百四十；五五数之剩三，置六十三；七七数之剩二，置三十。并之，得二百三十三，以二百十减之，即得。”“答日：二十三。”

它的系统解法是南宋数学家秦九韶在《数书九章·大衍求一术》中给出的。大衍求一术（也称作“中国剩余定理”）是中国古算中最有独创性的成就之一。

大衍求一术

大衍求一术其实就是列表，所谓求一就是找到余$1$的数，方法一共分为$3$步：

公倍数	1倍	2倍	3倍	4倍	……
[5,7]的倍数	35	70	105	140	……
[3,7]的倍数	21	42	63	84	……
[3,5]的倍数	15	30	45	60	……

1. 第一行为$5$、$7$的公倍数，第二行为$3$、$7$的公倍数，第三行为$3$、$5$的公倍数。
2. 在第一行中找到除以$3$余$1$的数：$70$，在第二行中找到除以$5$余$1$的数：$21$，在第三行中找到除以$7$余$1$的数：$15$
3. $70\times 2 + 21\times 3+15\times 2 =233$，$233-[3,5,7]\times 2=233-210=23$

这个算式的正确性是毋庸置疑的：

$70\times 2 + 21\times 3+15\times 2 \equiv 1\times 2+0+0 \equiv 2(\mod 3)$

$70\times 2 + 21\times 3+15\times 2 \equiv 0+1\times 3+0 \equiv 3(\mod 5)$

$70\times 2 + 21\times 3+15\times 2 \equiv 0+0+1\times 2\equiv 2(\mod 7)$

所以$233$是符合三个同余方程的数，只不过不是最小的，最后减去$3$、$5$、$7$的公倍数即可，不影响余数。

明代著名的大数学家程大位，在他所著的《算法统宗》中，对于这种解一般“孙子问题”的方法，以及$70$、$21$、$15$、$105$这几个数还编出了四句歌诀，名日《孙子歌》:

三人同行七十稀,
五树梅花廿一枝;
七子团圆正半月,
除百零五便得知。

但中国剩余定理也是有缺陷的，一是方程组的个数不宜太多，否则计算繁琐，二是除数必须两两互质，否则不可能找到余$1$的数。

逐级满足法

中国剩余定理解决更一般的同余方程问题计算着实麻烦，著名数学家陈景润在《初等数论Ⅰ》一书中给出了另外一个更好的方法，也就是逐级满足法，这个方法可以解决任意的同余方程组问题，无论除数是否互质，且计算上更加方便。

整数$a$满足$a\div 3\cdots\cdots2$，$a\div 5\cdots\cdots3$，$a\div 7\cdots\cdots2$，求$a$。

所谓逐级满足，就是两两满足，最终得到答案，比如先满足前两个方程，然后再满足第三个方程，如果有更多的，可以两两分组不断满足。逐级满足法是一个解法的思想，至于具体如何满足，最简单的可以枚举，复杂的可以用同余方程。

比如先找到除以$3$余$2$的和除以$5$余$3$的，枚举很容易发现是$8$，那么满足前两个方程的数就是$a\div 15 \cdots\cdots 8$，再满足$a\div 15 \cdots\cdots 8$和$a\div 7\cdots\cdots2$，枚举很容易发现是$23$。

如果用同余方程，设$a\div 3=x\cdots\cdots 2$，$a\div 5=y\cdots\cdots 3$，那么$a=3x+2$、$a=5y+3$则

$$\begin{align}
3x+2 &= 5y+3 \\
3x+2 &\equiv 5y+3 (\mod 3)\\
2 &\equiv 2y (\mod 3) \\
y &\equiv 1(\mod 3)
\end{align}$$

所以$a_{min}=5\times 1+3=8$，则$a\div 15 = z \cdots\cdots 8$，设$a\div 7 = w\cdots\cdots 2$，那么$a=15z+8$、$a=7w+2$则

$$\begin{align}
15z+8 &= 7w+2 \\
z+1 &\equiv 2 (\mod 7)\\
z &\equiv 1 (\mod 7) \\
\end{align}$$

所以$a_{min}=15\times 1+8=23$。