定理起源
这乃闻名于世的“物不知数”问题，记载于《孙子算经》（成书于公元 67-270 年之间），被誉为中国古代数学之经典。用现代数学语言表述为：“有一个数，被3除余2，被5除余3，被7除余2，问这个数是多少？答：该数为23” 现在我们带着23去验算，发现23确实符合题意，但是23是如何求得的呢？我们参考一下《孙子算经》对此题的解法：“三三数之剩二，置一百四十；五五数之剩三，置六十三；七七数之剩二，置三十。并之，得二百三十三，以二百十减之，即得。”“答曰：二十三。” 翻译：“被3除余2，找到140；被5除余3，找到63；被7除余2，找到30。全加起来，得到230，然后再减去210，得到最后答案23。” 当第一次读到这个答案的时候，确实感觉很“谜”，虽然得到了最后的答案，但是每一步都是那么的突兀，令人很费解。比如：为什么是140？63？30？为什么要减210？等等。如果我们对《孙子算经》的理解仅仅停留在这个层面上，那就大错特错了。 《孙子算经》记载了这一类题目的的通解：“凡三三数之剩一则置七十，五五数之剩一则置二十一，七七数之剩一则置十五，一百六以上以一百五减之，即得。”（注：古称“106”和“105”为“一百六”和“一百五”，而称“160”和“150”为“一百六十”和“一百五十”。所以，这里的“一百六”和“一百五”分别指“106”和“105”。） 翻译：当问题是关于除数是3、5、7的时候，如果被3除余1，则找到70（70能保证被3除余1，同时被5和7整除）；被5除余1，则找到21（21能保证被5除余1，同时被3和7整除）；被7除余1，则找到15（15能保证被7除余1，同时被3和5整除），最后答案如果比106大，那么就减去105。此算法给出了找到余数为1的方法。当问题要求我们求“余X”的数时，只要先求出“余1”的数，然后再乘以“X”就可以了。 回到“物不知数”问题，要求被3除余2，由于70满足“余1”，故70×2=140；要求被5除余3，由于21满足“余1”，21×3=63；要求被7除余2，由于15满足“余1”，15×2=30。最后要减的210，实际上是减了两遍105罢了。这就解释了《孙子算经》中的解法原理！ 方法虽然好，但是难记啊，中国人的智力水平马上就体现出来了，比如我们比较擅长编“顺口溜”，甚至是“诗歌”，明代的程大位就记录了一首“孙子歌”。什么？你不知道程大位？他可是 《算法统宗》的作者，珠算一代宗师，现如今的珠算技巧，均来自于程大位！
在这首歌诀中完全体现了该方法的精髓，“三人同行七十稀”中有数字3和70，如果是除以3的余数问题时，迅速找到70，后面的诗句同理。最后一句的“除”，实际是“减”的意思。得到该题的解法：N=70×2+21×3+15×2-105×2=23。 可能有些朋友对这个问题的解法还不是很理解，这里我们引入现代数学的观点，让大家更好的理解“物不知数”问题的精髓，为阅读下文做好铺垫！ 堆垒法（华罗庚用的方法）华老认为：“只要不是白痴，都能解得答案”根本在于根据条件逐步寻求满足条件的解，从三三数之剩二开始，先找到2，然后加3，得到5，由于5之满足第一个条件，但不满足第二个条件，所以再加3，直到找到既满足三三数剩二，又满足五五数剩三的数，自然会得到8。此时不需要再加3了，要加上前两个数的公倍数，即[3，5]=15，之后继续加15，直到这个数满足第三个（七七数之剩二）条件，此时我们会得到23。 这里我们不得不佩服华老，他老人家仅用加法就求出了答案，印证了“神奇化易是坦道”的名言。 集合观点写出三除余二的数，写出五除余三的数，写出七除余二的数，然后再找到同时满足这个三个条件的数。 三三数之剩二，设为集合A={2,5,8,11,14,17,20,23,26,…} 五五数之剩三，设为集合B={3,8,13,18,23,28,33,38,43,…} 七七数之剩二，设为集合C=｛2,9,16,23,30,37,44,51,58…｝ 同时满足三个条件的数是 A、B、C 中都有的数，也就是：A∩B∩C＝｛23，128，233，…｝，故符合此题解的最小正整数为 23。 希望以上两个处理方法能更好的帮助大家理解“物不知数”问题的核心，同时也能更好的理解这个歌诀的道理所在。 我们把时间轴再拉回到古代，一直以来，歌诀或者算法看似解决了问题，实则不然，因为这个口诀只适合除数是3,5,7的情况。当除数被更改的时候，立马出现的了新的问题，比如：“有一个数，被5除余2，被7除余3，被11除余2，问这个数是多少？”甚至说一个小学水平的人，都能如法炮制的出一个新的问题，同时这个问题非常难解！ 还是需要一个更加系统的解法，问题由中国人提出，自然由中国人去解，经过几代人的努力，在宋朝终于诞生了系统的解法，叫“大衍求一术”，它的创始人就是我们今天的主角--秦九韶！ 独特智慧--大衍求一术秦九韶（约1208-1268）自称鲁郡人，他沿用《孙子算经》的思想，核心还是要找到类似70，21，15的数，也即重点要找到那些令余数是1的数。从现代数学的角度看，该算法相当于求使ak≡1(mod p)的k(即乘率)，比如在“物不知数”问题中，为了寻找70,21,15这个几个数，可以构建同余方程：35k≡1(mod 3)； 21k≡1(mod 5)；15k≡1(mod 7)。如果通过试验的方法，我们可以得到k分别是2，1，1，这三个k值就是关键所在，如果找到k值，那么“物不知数”问题便可破解。这么关键的数，秦九韶先生把它命名为“乘率”（k值）。接下来的任务就找到“乘率”的算法了。千万不要以为这很简单，只是上面几个数比较小而已，如若遇到27k≡1(mod64)这样的问题，试数的方法可真是不灵了！ 功夫不负有心人，秦九韶找到了，并把这个算法命名为“大衍求一术”，记录在《数书九章》中。原文如下：
很多小朋友看到这又要炸裂了，本来数学就够难了，怎么还搞出一篇古文？不要着急，先用用一个图来说明这些名词！ 置奇右上，定居右下，立天元一于左上 先以右上除右下，所得商数与左上一相生，入左下 解释：作64÷27=2……10，余数10留在右下角，商数2与左上的1相乘，放入左下位置，形成第二个图！ 然后乃以右行上下以少除多，递互除之。所得商数随即递互累乘，归左行上下 继续操作：27÷10=2……7，余数7留在右上角，商数2与左下角的2相乘，归入左上位置，即2×2+1=5。 须使右上末后奇一而止。乃验左上所得，以为乘率。或奇数已见单一者，便为乘率 一直这样操作过去，直到右上角的数变成1后，左上角的数就是“乘率”，然后做一下检验：19×27=513，而513÷64=8……1，成立！ 意犹未尽的朋友可以做一下练习：求k，使得20k≡1（mod 27）。 根据“大衍求一术”可绘制上表，答案k=23. “大衍求一术”的厉害之处在于它的操作过程一定是“有限步”，这里的“有限”不同于现代数学上的“有限”，如果是天文数字般的“有限”，对实际问题是毫无意义的。同时，“大衍求一术”的算法机械、统一，只要按照步骤去操作就一定能正确输出结果，这就是现代计算机的运行思路，所以“大衍求一术”可以一字不差地搬到现代电子计算机上去实现。可以看出秦九韶对算法的研究简直是登峰造极！ 名字确立--中国剩余定理众所周知，中国古代数学经常出现比较尴尬的情形，有些定理在中国叫一个名字，在外国却叫另一个名字，比如中国叫“祖暅原理”，西方叫“卡瓦列利原理”，好像总是有争议的样子，一旦出现没争议的情况，大部分的定理都是西方人的名字，比如“韦达定理”，“泰勒公式”。冠有中国人名字的定理真是少之又少！那么秦九韶的“大衍求一术”是否又被外国人抢占了先机呢？答案是：NO！ 在十八九世纪，欧拉和高斯对一次同余方程问题给出了系统的解法，到了1852年英国传教士伟烈亚力，将“大衍求一术”的解法带到了欧洲，学者发现欧拉和高斯两位大神研究的解法和我们秦九韶先生的解法一致。欧拉和高斯竟然输给了500年前的神秘东方人！这一次，在定理的命名上，毫无争议！ 在中国，有人叫它“孙子定理”，因为它最早出自《孙子算经》，或者“秦九韶定理”，因为给出解法的人是秦九韶。但是放眼全世界，它的名字只叫“Chinese remainder theorem”，（中国剩余定理），它永远是最闪亮的一颗星，在数学界闪闪发光！ 【参考文献】 1杨国选．秦九韶生年及任西安尉考[J].中国科技史杂志，2008，29( 4):371～375． 2秦九韶．数书九章[M].北京中国国家图书馆藏明万历四十四年赵琦美钞本． 3秦九韶． 数书九章[M].∥四库提要著录丛书.子部020.北京:北京出版社，2011.96～325． 4秦九韶．数书九章[M].∥郭书春.中国科学技术典籍通汇·数学卷.第 1 册.郑州: 河南教育出版社，1993.439～724． 5 Libbrecht U.Chinese Mathematics in Thirteenth Century:The Shu-shu chiu-chang of Ch'in Chiu-shao[M].New York: Dover Publications，2005.372． 6吴文俊．秦九韶与《数书九章》[C].北京:北京师范大学出版社,1987． 7 Needham J，Wang L.Science and Civilisation in China．Volume 3: Mathematics and the Sciences of the Heavens and the Earth[M].Cambridge: Cambridge University Press,1959.119～122． 8钱宝琮.中国数学史[M].北京:科学出版社,1964.78～79． |
|
|
