昨天的文章里,一堆恼人的山楂让我们抓狂,今天,咱们来威风一把。咱们试着当一当汉高祖刘邦的手下大将——韩信,今天,韩信的任务是:点兵。

韩信点兵原来是数论故事 余数问题之二韩信点兵(1)

古代士兵玩偶

问题是:如果韩信带了一小队士兵,第一次3个人站一排,不足3个人时,将余数记下来;第二次5个人站一排,不足5个人时,将余数记下来;最后7个人站一排,不足7个人时,将余数记下来。然后,根据每次的余数,就可以知道有多少士兵。

韩信点兵原来是数论故事 余数问题之二韩信点兵(2)

古代士兵雕像

咱们将韩信、士兵这些元素去掉,将它变成一个数学问题。如果说,一个数除以3的余数是2,除以5的余数是1,除以7的余数是5,那么,这个数是多少呢?这个题目,看起来是很难的。可是,聪明的古人早就找出了解决的办法。

韩信点兵原来是数论故事 余数问题之二韩信点兵(3)

孙子算经

最初记载这个算法的,是一本名叫《孙子算经》的书,其实,这个问题在数学史上是非常有名的,一般人将它称之为“中国剩余定理”,也叫“孙子定理”。至于它的算法,流传着这样一首歌诀。

韩信点兵原来是数论故事 余数问题之二韩信点兵(4)

“韩信点兵”的计算方法歌诀

这是什么意思呢?就是说,凡是用3除剩下的余数,将它乘70,用5除的余数乘21,用7除的余数乘15,将这些数加起来,如果比105大,就减掉105,如果还是比105大,那就再减105,直到得数比105小为止。

韩信点兵原来是数论故事 余数问题之二韩信点兵(5)

拜将台

咱们来算算我开始提出的那个问题。2*70 1*21 5*15=236,236-105-105=26。算一下,是不是26除以3余2,除以5余1,除以7余5呢?没错!其实,236也满足这个条件,236-105=131也满足这个条件。不过,这是为什么呢?

韩信点兵原来是数论故事 余数问题之二韩信点兵(6)

数学有意思

咱们再来想想,为什么“韩信点兵”要用3、5和7这三个数呢?用别的数行不行?“中国剩余定理”的原理是什么呢?我们来试着将这个问题变成纯粹的数学问题,实际上就是,假设一个数是m,它被3除余x,被5除余y,被7除余z,这个数最小是多少呢?

韩信点兵原来是数论故事 余数问题之二韩信点兵(7)

宋朝数学家秦九韶

如果按照“韩信点兵”的办法,实际上就是,第一步,求m=70x 21y 15z,第二步,如果m比105大,就减去105或者105的若干倍,直到结果比105小。如果取x=1,y=2,z=3,那么m=70*1 21*2 15*3=157。157-105=52,52就是得数了。

韩信点兵原来是数论故事 余数问题之二韩信点兵(8)

快乐数学

我们拿上面这个例子,来说说为什么可以这样解题。问题的关键在于,歌诀里的70、21、15、105这四个数,和3、5、7之间的关系。为什么要选70呢?咱们来看,它非常特殊,你有没有发现,第一,它是5和7的公倍数,第二,它除以3的余数正好是1,70=3*23 1。

韩信点兵原来是数论故事 余数问题之二韩信点兵(9)

数字里藏着什么秘密呢?

继续来看,21这个数呢,你一定发现了,它是3和7的公倍数,而且,它除以5也余1,15呢?它是3和5的公倍数,而它除以7,正好也是余1!而105呢,它正好是3、5、7的最小公倍数!谜底似乎就要揭开了!按照我开始的设定,咱们可以从下图看出其中的道理。

韩信点兵原来是数论故事 余数问题之二韩信点兵(10)

列式计算

可以看出,m-105除以3的余数,确实是x。同样的道理,可以算出m-105除以5的余数是y,除以7的余数是z。是不是就得出答案了呢?不过,尽管知道了答案,喜欢刨根问底的人又会说,5和7的公倍数为什么要满足除以3余1呢?同样的道理为什么要适合另外两个数呢?

韩信点兵原来是数论故事 余数问题之二韩信点兵(11)

韩信塑像

这个问题问得非常好!咱们观察一下,其实,3、5和7这三个数,互为互质数,也就是说,这三个数的最大公约数是1。咱们观察一下上面的等式,就能发现,其中两个数的公倍数去除另一个数余1,会使得等式成立。

韩信点兵原来是数论故事 余数问题之二韩信点兵(12)

有意思的数学

好了,咱们再看看,如果不用3、5、7这三个数,能不能使用“韩信点兵”的方法呢?我找出2、3、5三个数,它们互为互质数。与3、5、7相对应的70、21、15和105,在2、3、5这里是多少呢?答案是15、10、6和30。看一看,是不是符合之前的条件呢?

韩信点兵原来是数论故事 余数问题之二韩信点兵(13)

新的“韩信点兵”

咱们来试着算一下,如果一个数,用2除余1,用3除余2,用5除余3,这个数是多少呢?用咱们得到的数字15*1 10*2 6*3-30=23,23除以2余1,除以3余2,除以5余3,正好!所以,咱们找的数正是23。

,