吃着热狗就把数学整明白了？_风闻

原创：中科院物理所

中国剩余定理是关于最小公倍数的一个古老而强大的扩展。

如果你曾经为了户外烧烤而买过热狗，你可能会发现自己正在解一道涉及最小公倍数的数学题。这里涉及的问题是：为什么通常一袋热狗有 10 根，而一袋面包却只有 8 块？这使得我们需要用数学的方法搭配热狗和面包的数量。

一个简单的解决办法是买 8 袋热狗和 10 袋面包，但谁会需要 80 根热狗呢? 那么，你能买更少的袋数，仍然使热狗和面包的数量相匹配吗?

让我们列出通过购买不同袋数而获得每种物品的数量。

每个列表上都有一个 40 ，因为 40 是 10 和 8 的**最小公倍数(LCM)——它是能被这两个数字整除的最小正整数。**如果你买 4 袋热狗和 5 袋面包， 40 根热狗就会和 40 个面包完美搭配。

但如果热狗的包装是一袋有 5 根（质数数量），而且 40 个热狗超过了你的需求，那该怎么办?你还有比买 8 袋热狗 5 袋面包更简单的方法吗?下图是新的列表。

在这种情况下，热狗和面包的数量达到 40 之前是不匹配的，因为 40 是 5 和 8 的最小公倍数。这是因为 5 和 8 “互质”——它们的公因数只有 1。**当两个数互质时，最小公倍数就是它们的乘积。**当你开始列出8的倍数—— 8 × 1 ， 8 × 2 ， 8 × 3 ， 8 × 4 ， 8 × 5 ——你可以看到，除了 8 × 5 之外没有其他 5 的倍数。

但是，当两个数不是互质整数时，它们的公倍数有机会在达到两者乘积之前匹配起来。

在第一个例子中，10 和 8 不是互质的，因为它们都有一个因子—— 2 ：

10 = 2 × 5，

8 = 2 × 4，

因为 8 已经能被 2 整除，所以你只需要找到一个 8 的倍数，让它能被 5 整除，这个数就能被 10 整除。这就是为什么最小公倍数为 8 × 5 = 40 ，而远未达到 8 × 10 = 80 。

现在假设你去商店之前发现冰箱里剩了一根热狗，那么你要再分别买多少袋热狗和面包来搭配?

这个新问题超越了简单的最小公倍数问题，进入了更为复杂的中国剩余定理领域。

中国剩余定理最早是由中国数学家孙子在约2000年前提出的。中国剩余定理存在于一个叫做模算术的数学领域，该领域通过分析数被其他数除后的余数来研究数学，被用于从密码学到天文学的多个领域。让我们看看热狗和最小公倍数如何帮助我们理解这个古老的算法。

如果你冰箱里有一根热狗，你可以在商店里买每袋 5 根的热狗，下面列出了你可以带出去野餐的热狗数量:

因为热狗的数量总是 1 加上 5 的倍数，所有这些数除以 5 的余数都是 1 。令 x 等于热狗的数量，这个关系式可以写成：

x ≡ 1 mod 5.

表述为“整数****x 与 1 对模 5 同余”，意思是 x 除以 5 余数为 1 。你也可以说“ x 同余于 1 模 5 ”。

因为面包的数量总是 8 的倍数，所以除以 8 的余数总是 0 。如果 y 是热狗面包的数量，这个关系式可以写成：

y ≡ 0 mod 8.

我们想要热狗的数量和面包的数量相等，所以要求 x = y ，为了找出什么时候成立，我们可以解出下面的方程组：

x ≡ 1 mod 5x ≡ 0 mod 8

在一个方程组中，解一个同余方程组的目标是同时满足所有的同余。

我们想要找到一个数 x ，当它除以 5 时余数为 1 ，且当它除以 8 时余数为 0 。如果能做到这一点，我们的热狗和面包就能完美搭配。

中国剩余定理就是用来处理这类系统的。它告诉我们，只要两个除数（也称为模）是互质数，不管余数是多少，就有一个大于或等于零但小于模乘积的唯一解。(如果两个模不是互质的，则可能没有答案。例如， x = 1 mod 6 和 x = 2 mod 8 的方程组没有解，无论是小于 24 还是大于 24 。)因为 5 和 8 是互质整数，所以这个方程组应该有一个小于 40 的唯一解。

这个问题中的数字很小，所以我们可以通过列出热狗和面包的可能数量来找到答案：

如你所见，两个表上都有小于 40 的数 16 ，这便是方程组的解。我们可以很快地检查， 16 除以 5 的余数是 1 、除以 8 的余数是 0 。（注意，如果你把 40 ,也就是 5 和 8 的最小公倍数加上 16 ，你得到的 56 便是下一个方程组的解。）

中国剩余定理不仅保证了解的存在，而且还给出了求解的方法。该算法依赖于这样一个事实：如果两个数互质，你总能找到它们的整数组合等于 1 。

让我们看看这如何应用于另一个野餐问题。

想象一下，除了一个吃剩的热狗，你还有两个吃剩的面包。现在你要买多少包热狗和面包才能匹配得上这些东西?

为了回答这个问题，我们需要解出以下的同余方程组：

x ≡ 1 mod 5x ≡ 2 mod 8

为了找到由中国剩余定理确定的解，我们将使用这样一个事实：**因为 5 和 8 是互质数，它们的某个线性组合为 1 。**这句话的意思是，**我们可以找到整数 a 和 b ，使 5a + 8b = 1 。**你可以很容易地检查 a = −3 和 b = 2 是否满足：

5 × ( -3 ) + 8 × 2 = 1.

为了找到我们的解，中国剩余定理的算法告诉我们，用5 × ( -3 ) 乘以面包的余数 2 ，用 8 × 2 乘以热狗的余数 1 ，然后把结果相加：

2 × 5 × ( -3 ) + 1 × 8 × 2 = -14.

就是说，我们最后可以吃到 −14 个热狗和 −14 个面包来进行匹配的热狗面包，这听起来像一个关于数学家计划野餐的垃圾笑话的笑点。但其实我们真正的解就藏在这里。记住，我们知道 8 袋热狗和 5 袋小面包的值都是 40 （就像我们之前的例子中 16 和 56 的解一样），所以我们只需要把 40 加 −14 得到 26 ， 26 便是大于 0 小于 40 的唯一解，而这便是由中国剩余定理决定的。

你可以看到， 26 个热狗和 26 个面包解决了这个问题，如果你把每一个可能的数字列出来:

有一个简单而巧妙的理由来解释中国的余数定理为什么成立。要知道为什么，想想所有小于 5 和 8 最小公倍数 40 的 5 的倍数：

这些倍数是 0 × 5 ， 1 × 5 ， 2 × 5 ， 3 × 5 ， … ，和 7 × 5 ，共有 8 个大于等于 0 但小于 40 的 5 的倍数。因为这些倍数都小于最小公倍数 40 ，所以当它们被 8 整除时，余数肯定是不同的；如果其中任意两个数除以 8 的余数相同，那么它们的差就能被 8 整除，两个 5 的倍数之差也是 5 的倍数，于是这个差必然能被 5 和 8 同时整除，这样就能被 40 整除。这是不可能的，因为小于 40 的两个 5 的倍数不可能是 40 。

看看这里所有不同的余数：

因为除以 8 只有 8 个可能的余数，所有可能的余数都会出现在这个列表上。这意味着 5 在 40 以下的倍数包含了对 8 取余的所有可能的余数。换句话说，如果你冰箱里剩下的面包数量小于一袋，你就能做出少于 40 个热狗。数学上用同余方程组表述：

x ≡ 0 mod 5x ≡ a mod 8

对于任意 a ，解总是小于 40 ，只要检查一下上面的余数列表：对于 a = 1 ，解是 x = 25 ；对于 a = 2 ，解是 x = 10 ，以此类推。

如果你一开始多一个热狗呢? 每当热狗数增加 1 时，余数增加 1 。但是因为所有的余数同时被移动了 1，所以所有 8 个可能的余数仍然可以被表示出来。

注意，余数7向上移 1 等于 7 + 1 = 8 ，如果一个数除以 8 的余数是 8 ，那么它实际上是 8 的倍数，所以余数实际上是 0 对 8 取余。

这意味着同余方程组：

x ≡ 1 mod 5x ≡ a mod 8

也有一个小于 40 的解，对于 a = 1 ，解是 x = 1 ；对于 a = 2 ，解是 x = 26 ，以此类推。

这个推理可以概括为：

x ≡ b mod 5x ≡ a mod 8

对于每一个 a 和 b 都有一个小于 40 的解，并进一步推广以证明每个同余方程组的形式：

x ≡ b mod mx ≡ a mod n

**只要 m 和 n 互质，**就存在一个小于 m × n 的解。这是中国剩余定理最基本的内容。

这个定理和许多数论技巧一样，在密码学中很有用，密码学是编码和解码秘密信息的数学。例如，你可以使用这个定理对一个数字加密，需要一组人共同合作来识别它。

假设你有一个想要保密的数字，在你的朋友张三和李四一起同意他们想知道这个数字后才能解密。首先给他们分配一对互质数——比如，张三和李四分别是 13 和 17 ——它们的乘积大于你的秘密数字。现在用你的数字除以他们每个人的数字，给他们每个人各自的余数。他们各自都不会知道你的数字，但他们肯定能一起算出来，这要感谢中国剩余定理！

假设你告诉张三的是 11 ，告诉李四的是 15 。这意味着张三知道你的数 x 满足 x ≡ 11 mod 13 ,李四知道 x 满足 x ≡ 15 mod 17 。这两个方程单独都不足以确定你的密码，但它们一起构成了这个同余方程组：

x ≡ 11 mod 13x ≡ 15 mod 17

而中国剩余定理保证了该方程组有一个小于 13 × 17 = 221 的唯一解。张三和李四一起合作，就能算出你的号码是 219 。

你可能不需要中国剩余定理来计划你的下一次野餐，但如果你需要在你的朋友之间分享信息或秘密地与你的将军分享部队数目，那你最好确保这个中国剩余定理在你的计划当中。