第五讲 中国剩余定理在线视频

欢迎大家来到数学文化的课堂

这堂课我们来谈谈数学文化之中国剩余定理

首先呢我们先听听两个典故

第一个便是韩信点兵的故事

这个故事主要是说

秦朝末年

楚汉相争

韩信率1500名将士与楚王大将李锋交战

苦战一场

楚军不敌

败退回营

汉军也死伤四五百人

于是韩信整顿兵马也返回大本营

当行至一山坡

忽有后军来报

说有楚军骑兵追来

只见远方尘土飞扬

杀声震天

汉军本来已十分疲惫

这时队伍大哗

韩信急速点兵迎敌

他命令士兵3人一排

结果多出2名

接着命令士兵5人一排

结果多出3名

他又命令士兵7人一排

结果又多出2名

此时韩信马上向将士们宣布

我军有1073人

敌人不足五百

我们居高临下

以众击寡

一定能打败敌人

那么

请问韩信是如何判断出军队中的总人数呢

其实不难发现

韩信是特别重视这些余数的

韩信在整个点兵的过程

主要经历了以下几步

首先

第1步

先列出满足其中一个条件的数

即除以3余2的数

2

5

8

11

14

17

20

23等等

然后

第2步再列出满足其中第二个条件的数

即除以5余3的数

3

8

13

18

23

28

等等

第三步主要将前2步的结果进行归纳发现

首先出现的公共数是8

这个8就是满足除以3余2

除以5余3的最小的那个数

而除数3与5的最小公倍数是15

两个条件一合并在一起就是8＋15×n

n=0，1，2…

再将满足这个式子的数字列出便是

8

23

38等等

第4步再列出满足其中第三个条件的数

即除以7余2的数

2

9

16

23

30等等

在第5步再将第3 4步的结果

进行同第三步相同的归纳

就得出符合题目条件的最小数是23

事实上

我们已把题目中三个条件合并成一个了

3，5，7的最小公倍数是105

满足三个条件的所有数是23+105×n

n=0，1，2…

最后

由于韩信点的兵在1000-1100之间

所以得出军队总人数1073人

听完第一个故事的方法原理后

我们再来看看我国古代数学名著《孙子算经》中

物不知数的问题

今有物不知其数

三三数之剩2

五五数之剩3

七七数之剩2

问物几何

这个题目是什么意思呢

其实就是说不知道是什么的物体

三个三个数剩2个

五个五个地数剩3个

七个七个地数剩2个

问这些物体有多少个呢

回答道有23个

通过上个故事的原理我们可以求解该问题

但是发现因为没有范围

所以结果有无数多个

那这个23是怎么被确定的呢

其实不难发现

它其实就是当n取0时的最小正整数解

一千多年前

我们的祖先将以上两个看似生活化的计算思路

进行严谨的数学描述和推导

得出了著名的中国剩余定理

其主要描述为

设d1d2一直到dn

两两互素

x分别被d1d2到dn除所得的余数为r1r2

一直到rn

则x可以表示为

x=K1·r1+K2·r2+···+Kn·rn+KD

其中D是d1d2···dn的最小公倍数

Ki是d1···di-1，di+1···，dn的公倍数

且被di除所得的余数为1

k是任意的正整数

特别注意只有在满足两两互素时

使用该公式得出的结论才成立

如三三数

五五数

七七数的余数可以用此公式

而四四数

六六数

九九数的余数就不能使用该公式

中国剩余定理

历史悠久

具有光辉的历史意义

1970年

28岁的苏联数学家尤里

解决了希尔伯特提出的23个问题中的第10个问题

不定方程

丢番图方程的可解答性

轰动了当时的世界数学界

他在解决这个问题时

用到的知识十分广泛

而在一个关键的地方

用到的便是我们中国的剩余定理

接下来我们来看一下这个题目

一起来体会有趣的中国剩余定理吧

某单位有100把锁

分别编号为1， 2，3…100

现在要对钥匙编号

使外单位的人看不懂

而本单位的人

一看见锁的号码就知道该用哪一把钥匙

能采用的方法其实有很多

其中一种就是利用中国剩余定理

较为简单的是我们可以把锁的号码

被3，5，7去除所得的三个余数

来作为钥匙的号码

但要注意

如果首位的余数为0时不能省略

保证钥匙的号码总是三位数

例如对8号锁的钥匙编码为2，3，1

而对45号锁的编码为003

之所以选择3，5，7是因为其两两互素

最小公倍数为105

而目前只有100把锁

所以每个锁的号与钥匙的号

是一个一一对应的关系

或许我们觉得这个编码方式也太简单了吧

即便我不是这个单位的我都可以轻松破解了

既然如此

大家下去思考一下

还可以怎样设计保密性更强的密码呢

这节课到这里我们就要结束了

数学的文化却远远不止于此

让我们下一节课再继续走进有趣的数学王国吧