一周一定理No.1 中国剩余定理


在最近推出的两篇文章


微积分之前奏1:高阶等差数列的求和

算命是胡扯,猜姓却不然


中,我们都提到了中国剩余定理,虽然我曾在


从射雕到九章——在天大理学院物理系的通俗报告


介绍过,但有点浮光掠影,我们想在此详细介绍一下。


我们期待,本文作为好玩的数学开创的头一个专栏——一周一定理——的开篇,能够打响第一炮。本专栏的开创,学习和借鉴了下述网页(感谢上海交通大学数学系吴耀琨教授向我们推荐)


1.jpg


有兴趣的读者,可以先浏览这个主页上的各个定理。欢迎各位读者为本专栏供稿,投稿邮箱在这里来,一起交流数学


好了,现在我们直奔主题。


中国剩余定理:设正整数m1,m2,…,mn两两互素,则下述同余方程组


2.jpg


(其中r1,r2,…,rn给定的整数)的整数解恰好是模

M=m1m2…mn

的一个剩余类。事实上,方程 (*) 的通解为

x=r1M1x1+…+rnMnxn+kM,k∈Z  (#)

其中Mi=M/mi而xi是同余方程

Mixi1(mod mi)    (*i)

的一个特解,因而可以用求一术得出。


简单地说,中国剩余定理将一个同余方程组(*)的求解,归结为多个一次同余方程(*i)的求解,而后者可以用求一术来求解。那么,什么是求一术呢?我们表述成一个算法的形式:


求解方程

3.jpg

的整数解的求一术:


首先写出矩阵

4.jpg

然后对第一行两个元素辗转相除,并将对应的操作应用于第二行,直至第一行某个元素变成0(停止信号),此时观察第一行的另一个元素:若它恰好是1(正常信号),则它下方的那个数就是(♣)的一个特解;否则,(♣)无整数解。此外,若已得到(♣)的一个特解,比方说,那么,(♣)的通解为


5.jpg


:我们不打算证明求一术,它本质上就是解线性方程组的矩阵变换方法。我们指出,在中国古代还未出现0时,通常是用辗转相减(即“更相减损术”),所以最后终止的信号是,出现的等数(即最大公因子)为1,这就是求术名称的来由(对此,请参见许光午和李宝[4])。另一方面,注意到方程(♣)本质上是在求逆,所以,也许一个更恰当的称谓是求逆术。由此可以理解,为什么在下述网页中,作者用了逆的记号来表述结果:


6.jpg


好了,现在我们来实战吧。首先,我们解释上述网页中的例子,即我们要求解同余方程组


7.jpg


为求解这个方程组,我们来求解两个更简单的方程组


8.jpg



9.jpg


先看(1),注意到(1)的第二个方程相当于说,x是5的倍数,因此我们可以令

10.jpg

从而代入(1)的第一个方程,就把(1)整个转化为一次同余方程

11.jpg

在这个特殊情况,我们可以直接看出(1*)的一个特解为

12.jpg

类似的,我们来求解方程组(2), 注意到它的第一个方程相当于说

13.jpg

从而(2)可化为线性方程


14.jpg

容易观察到,(2*)的一个特解为

15.jpg

(注:当然你也可以取x2=4,就像上述网页中那样)


因此,根据中国剩余定理,原方程组(0)的通解为


16.jpg


最经典的一个例子,即金庸曾在《射雕英雄传》原著中引用的“鬼谷算题”:

17.png

我们留给有兴趣的读者自行研究,其求解步骤,可以参考从射雕到九章——在天大理学院物理系的通俗报告


而在94版的射雕电视剧中,这个题目被编剧稍微改了改(参见下述链接最后部分),你能算出来吗,你猜神算子瑛姑能算出来吗?



18.jpg

19.jpg20.jpg


延伸阅读

[1] 华罗庚,从孙子的“神奇妙算”谈起,数学小丛书,北京,科学出版社。

[2] 蔡聪明,谈韩信点兵问题,《科学月刊》第29卷第9期。电子版可见数学知识网页:http://episte.math.ntu.edu.tw/

[3] 项武义,從韓信點兵和勾股弦說起一一漫談基礎數學的古今中外,《数学传播》,电子版http://web.math.sinica.edu.tw/math_media/d211/21101.pdf(建议在谷歌浏览器打开网页版,并开启翻译功能。近日我们会推出该文的简体版)

[4] 许光午,李宝,大衍求一术的算法意义与分析

https://arxiv.org/ftp/arxiv/papers/1610/1610.01175.pdf





0.356115s