一桩盗窃案

阅读(217)

数论中国古代数学

收录于

华山论剑 -- 2021年02月16日

摘要

大衍求一术和中国剩余定理可用于求解著名的"孙子问题——物不知数"，你听过大衍求一术吗？

早在公元四世纪前，我国数学著作《孙子算经》中就提出过著名的“孙子问题”：

“今有物不知其数, 三三数之剩二，五五数之剩三，七七数之剩二，问物几何？“也就是说

“有一数, 用3除它余2，用5除它余3，用7除它余 2，求这个数.”

用现代数学符号来记就是: 求一最小正整数 $\text{[math]}$ , 满足联立一次同余式: $\text{[math]}$ 这里，符号 $\text{[math]}$ 表示: $\text{[math]}$ 除以 $\text{[math]}$ 余 $\text{[math]}$ .

一般地, 符号 $\text{[math]}$ 表示: $\text{[math]}$ 除以 $\text{[math]}$ 余r 或者说, $\text{[math]}$ 与 $\text{[math]}$ 同除以 $\text{[math]}$ , 其余数相等.

这个问题怎么求解呢？需要用到大衍求一术和中国剩余定理.

什么叫大衍求一术呢？通俗讲就是求”一个数的多少倍除以另一数, 所得余数为 $\text{[math]}$ ”的方法,即求“ $\text{[math]}$ 中的 $\text{[math]}$ 的方法. 称 $\text{[math]}$ 为乘率.

大衍求一术是公元1247年，南宋数学家秦九韶在《数书九章》一书记载的一种著名的方法，他用这种方法解联立一次同余式问题，获得了很好的效果，给中国和世界数学史增添了光辉的一页.

例如：求解: $\text{[math]}$ mod 83 $\text{[math]}$ .

即2970的多少倍除以83，所得余数为1?

具体操作步骤如下：

$\text{[math]}$

由此得出 $\text{[math]}$ 注：当 $\text{[math]}$ 左式的余数为1，且n为偶数时，那么 $\text{[math]}$

当 $\text{[math]}$ 左式的余数为1，且n为奇数时，那么 $\text{[math]}$

大衍求一术和现代的求最大公约数的辗转相除法类似，至于具体原理，在此不再说明，有兴趣的可查阅参考文献.

回到“孙子问题”：“有一数, 用 $\text{[math]}$ 除它余 $\text{[math]}$ ，用 $\text{[math]}$ 除它余 $\text{[math]}$ ，用 $\text{[math]}$ 除它余 $\text{[math]}$ ，求这个数.”

“第一步，先将问题转化为求三个数，分别是

① $\text{[math]}$ 除余 $\text{[math]}$ ， $\text{[math]}$ 和 $\text{[math]}$ 能除尽；② $\text{[math]}$ 除余 $\text{[math]}$ , $\text{[math]}$ 和 $\text{[math]}$ 能除尽；③ $\text{[math]}$ 除余 $\text{[math]}$ , $\text{[math]}$ 和 $\text{[math]}$ 能除尽.

①这个问题就是求解同余式 $\text{[math]}$ mod 3 $\text{[math]}$ ，我们用大衍求一术来解 $\text{[math]}$ 所以， $\text{[math]}$ ,显然 $\text{[math]}$ .

也就是 $\text{[math]}$ 被 $\text{[math]}$ 除余 $\text{[math]}$ .

② $\text{[math]}$ 除余 $\text{[math]}$ , $\text{[math]}$ 和 $\text{[math]}$ 能除尽，这个可以猜一下， $\text{[math]}$ 就是符合条件最小的数，所以不需要用大衍求一术求解了.也就是 $\text{[math]}$ 被 $\text{[math]}$ 除余 $\text{[math]}$ .

③同②， $\text{[math]}$ 除余 $\text{[math]}$ , $\text{[math]}$ 和 $\text{[math]}$ 能除尽, 这个数是 $\text{[math]}$ .也就是 $\text{[math]}$ 被 $\text{[math]}$ 除余 $\text{[math]}$ .

第二步，① $\text{[math]}$ 被 $\text{[math]}$ 除余 $\text{[math]}$ , 于是 $\text{[math]}$ 被 $\text{[math]}$ 除余 $\text{[math]}$ . ② $\text{[math]}$ 被 $\text{[math]}$ 除余 $\text{[math]}$ ,于是 $\text{[math]}$ 被 $\text{[math]}$ 除余 $\text{[math]}$ . ③ $\text{[math]}$ 被 $\text{[math]}$ 除余 $\text{[math]}$ ，于是 $\text{[math]}$ 被 $\text{[math]}$ 除余 $\text{[math]}$ .

也就是用70乘以“用 3 除所得的余数 2”得 140，21 乘以 “用5除所得的余数3”得63,15乘以“用7除所得的余数2”得30,然后加起来得233.

注意到 $\text{[math]}$ 是互为质数的，因此总和 $\text{[math]}$ 是满足题目条件的一个数.

又 $\text{[math]}$ 于是一般的通解为 $\text{[math]}$ 满足条件的最小正整数为 $\text{[math]}$ $\text{[math]}$ 其实第二步，就是应用“中国剩余定理”：下列联立一次同余式 $\text{[math]}$ 的解为 $\text{[math]}$ (其中 $\text{[math]}$ 为整数)