中国剩余定理是关于最小公倍数的一个古老而强大的扩展。如果你曾经为了户外烧烤而买过热狗，你可能会发现自己正在解一道涉及最小公倍数的数学题。这里涉及的问题是：为什么通常一袋热狗有10根，而一袋面包却只有8块？这使得我们需要用数学的方法搭配热狗和面包的数量。一个简单的解决办法是买8袋热狗和10袋面包，但谁会需要80根热狗呢？那么，你能买更少的袋数，仍然使热狗和面包的数量相匹配吗？
让我们列出通过购买不同袋数而获得每种物品的数量。每个列表上都有一个40，因为40是10和8的最小公倍数(LCM)——它是能被这两个数字整除的最小正整数。如果热狗的包装是一袋有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 5，x ≡ 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 5，x ≡ 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 5，x ≡ 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 5，x ≡ a mod 8。也有一个小于40的解，对于a = 1，解是x = 1；对于a = 2，解是x = 26，以此类推。这个推理可以概括为：x ≡ b mod 5，x ≡ a mod 8。对于每一个a和b都有一个小于40的解，并进一步推广以证明每个同余方程组的形式：x ≡ b mod m，x ≡ a mod n。
只要m和n互质，就存在一个小于m × n的解。这是中国剩余定理最基本的内容。这个定理和许多数论技巧一样，在密码学中很有用，密码学是编码和解码秘密信息的数学。例如，你可以使用这个定理对一个数字加密，需要一组人共同合作来识别它。假设你有一个想要保密的数字，在你的朋友张三和李四一起同意他们想知道这个数字后才能解密。
首先给他们分配一对互质数——比如，张三和李四分别是13和17——它们的乘积大于你的秘密数字。现在用你的数字除以他们每个人的数字，给他们每个人各自的余数。他们各自都不会知道你的数字，但他们肯定能一起算出来，这要感谢中国剩余定理！假设你告诉张三的是11，告诉李四的是15。这意味着张三知道你的数x满足x ≡ 11 mod 13,李四知道x满足x ≡ 15 mod 17。
这两个方程单独都不足以确定你的密码，但它们一起构成了这个同余方程组：x ≡ 11 mod 13，x ≡ 15 mod 17。而中国剩余定理保证了该方程组有一个小于13 × 17 = 221的唯一解。张三和李四一起合作，就能算出你的号码是219。你可能不需要中国剩余定理来计划你的下一次野餐，但如果你需要在你的朋友之间分享信息或秘密地与你的将军分享部队数目，那你最好确保这个中国剩余定理在你的计划当中。