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

中国剩余定理

中国剩余定理又称孙子定理,是中国古代求解一次同余式组的通用方法。同余方程组问题最早可见于中国南北朝时期(公元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$。

© 版权声明
THE END
喜欢就支持一下吧
点赞6 分享
评论 抢沙发
头像
欢迎做题
提交
头像

昵称

取消
昵称表情代码图片

    暂无评论内容