如果你在为外出野餐时购买热狗的原料：面包和热狗肠，你可能会意识到自己正在解决一个涉及最小公倍数的数学问题。暂且不谈为什么热狗肠通常是10个一袋，而面包是8个一袋。现在让我们计算一下在例子1的情况下需要多少袋热狗肠和面包才能够让热狗肠和面包正好用完做成热狗。
一个简单的解决办法是买8包热狗肠和10包小面包，但谁需要80个热狗呢？能不能够购买更少袋数的热狗肠和面包，但仍保持热狗肠和面包的数量匹配呢？
让我们列出购买的包数和对应包数的食物数量。每个数列上都有一个40，因为40是10和8的最小公倍数(least common multiples, LCM)——它是能被两个数平均整除的最小数。如果你买4袋热狗肠和5袋小面包，那40个热狗肠和40个小面包就完全匹配了。
但是，如果热狗是5个一组的，甚至40个也超过了你的需要，那该怎么办？你还有比买八包热狗五包小圆面包更简单的方法吗？以下是新的表单：在这种情况下，热狗和面包在达到40之前是不匹配的，因为40是5和8的最小公倍数。这是因为5和8是“互质”的——它们没有共同的因数（除了1）。当两个数互质时，它们的最小公倍数就是它们的乘积。
如果我们列出——8 × 1， 8 × 2， 8 × 3，8 × 4， 8 × 5时，我们就会发现在8 × 5之前没有可能热狗肠和面包数量一致。在例子1中，10和8不互质，因为它们共享一个因子——2。也就是10 = 2 × 5， 8 = 2 × 4。因为8已经能被2整除，你只需要一个8的倍数能被5整除，这个数就能被10整除。这就是为什么在8 × 5 = 40时，倍数就首先匹配了。
现在想象一下从冰箱里剩下的一个热狗开始，你必须买多少包热狗和面包来搭配？这个新问题并不是让我们简单地寻找最小公倍数，而需要使用稍微复杂一些的——中国余数定理。中国余数定理是中国数学家孙子在约2000年前首先发现的一元线性同余方程组有解的准则和求解方法，古有“韩信点兵”，“物不知数”之名。
中国余数定理属于数学领域中的模运算，通过分析数除以其他数后的余数来研究数字。它被用于从密码学到天文学的各种领域中。让我们看看热狗和最小公倍数如何帮助我们理解这个古老的算法。
如果你冰箱里有一个热狗肠，你还可以在商店里买5个一包的热狗，以下是你可以带出去野餐的热狗数量：因为热狗肠的数量总是1加上5的倍数，所有这些数字除以5余数都是1。让x表示热狗肠的数量，你可以把这个关系写成x≡1 mod 5。你可以把它理解为“x等于1 mod 5”意思是当x除以5时余数是1。你也可以说“x模5余1”。
因为面包的数量总是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的解。
刚才所说的这个问题的数量很小，所以我们可以通过排列热狗和面包的可能数量来找到答案：如你所见，两个表上都有16，小于40，解出了同余方程组。我们可以快速检查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——唯一大于0但小于40的解。这是由中国余数定理得出的。
你可以看到26个热狗和26个面包解决了这个问题，如果你把每个可能的数字排列起来：中国余数定理的成立有一个简单但智慧的证明。想想40以下5的所有倍数：这些倍数分别是0 × 5、1 × 5、2 × 5、3 × 5、……和7 × 5，所以有8个大于或等于0但小于40的5的倍数。由于这些5的倍数都小于最小公倍数，所以当除以8时，它们的余数一定都不同。
如果其中任意两个除以8的余数相同，那么它们的差就能被8整除。但是两个5的倍数之差也是5的倍数，所以这个差必须能被5和8整除，这样就能被40整除。这是不可能的，因为两个小于40的5的倍数之间的距离不可能是40。看看这里所有不同的余数：因为除以8时只有8个可能的余数，所有可能的余数都出现在这个表上。这意味着40以下5的倍数涵盖了所有可能的余数对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的倍数，所以对8取余后余数实际上是0。
这意味着同余方程组x ≡ 1 mod 5，x ≡ a mod 8，对于每一个a，也有一个小于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的解。这是中国余数定理的最基本的内容。
这个定理，就像许多数论技巧一样，在密码学中非常有用。
让我们来举个栗子：比如你心里想了一个数字，让好友Alex和Bo来猜猜看，除非你的朋友Alex和Bo都同意他们都想知道它，否则不能解开这个秘密数字。那你应该怎么做呢？首先给它们分配一对互质的数——比如Alex的13和Bo的17——它们的乘积大于你的秘密数字。现在用你的数字除以他们每个人的数字，给他们每个人各自的余数。他们都不知道你的数字，但他们保证能够一起算出来，这真的要感谢中国余数定理！
假设你告诉Alex数字11，告诉Bo数字15。这意味着Alex知道你的数x满足x≡11 mod 13，而Bo知道x满足x≡15 mod 17。单独一个同余方程都不足以确定你的密码，但它们一起构成了这个方程组：x ≡ 11 mod 13，x ≡ 15 mod 17。中国余数定理表明该方程组有一个小于13 × 17 = 221的唯一解。只要Alex和Bo愿意合作，就能算出你的秘密数字是219。
你可能不需要用中国余数定理来计划你的下一次野餐，但如果你需要在你的朋友之间分发信息，或者与你的将军秘密地分享兵力，那么——确保你还能回忆起这个和热狗有关的奇妙定理吧！
练习时间01请解释为什么这个同余方程组没有解：x ≡ 1 mod 4，x ≡ 0 mod 6。为什么这没有违反中国余数定理？答案点击下方空白处获得答案（可向下滑）只有奇数满足x≡1 mod 4，只有偶数满足x≡0 mod 6，所以这个同余方程组没有解。这并不违反中国余数定理，因为模4和6不是互质的。
02解决热狗的问题时x ≡ 1 mod 5，x ≡ 2 mod 8我们利用了(-3)× 5 + 2 × 8 = 1的事实。而13 × 5 + (-8) × 8 = 1也是正确的。如果我们用这个整数组合会发生什么？答案点击下方空白处获得答案（可向下滑）应用该算法，我们将13 × 5乘以面包余数(2)，(-8)× 8乘以热狗余数(1)，得到2 × 13 × 5 + 1 × (-8) × 8 = 66。
同样地，我们总是可以匹配40个热狗和面包，我们从66中减去40得到26，还是原来的解。
03考虑这个同余方程组：x ≡ 1 mod 3，x ≡ 2 mod 4。求这个方程组的三个正数的解。所有这些数对12取余都是一样的。它是什么？答案点击下方空白处获得答案（可向下滑）通过检查你可以看到10是一个解决方案。你也可以加上LCM(3)和LCM(4)，也就是12，来得到其他的解，比如22、34等等。
因此解决方法是x ≡ 1 mod 3，x ≡ 2 mod 4，所有解都满足x≡10 mod 12。
04用练习3的结果来解这个同余方程组：x ≡ 1 mod 3，x ≡ 2 mod 4，x ≡ 3 mod 5。答案点击下方空白处获得答案（可向下滑）如练习3所示，你可以把前两个同余的式子结合起来得到x≡10 mod 12。现在你可以解这个方程组了x ≡ 3 mod 5，x ≡ 10 mod 12。
注意5 × 5 + (-2) × 12 = 1，所以一个解是10 × 5 × 5 + 3 × (-2) × 12 = 178。你也可以减去60 (LCM为12和5，LCM为3、4和5)来得到更小的解，比如118和58。这也将中国余数定理推广到涉及两个以上同余的方程组。恭喜你完成训练！