中国剩余定理：让两份余数记录对上
桌上有一堆小圆片，我们不知道总数。每三个分成一组，会剩两个；重新把全部圆片按每五个一组来分，会剩三个。两次记录说的是同一堆圆片。那么，哪些总数能够同时满足它们？
中国剩余定理研究的正是这类问题：知道一个整数分别除以几个数的余数，怎样把这些信息合起来？[[divisibility|整除]]页面讲过怎样用除法留下余数；这里从数圆片重新开始，所以那一页不必先读。我们会把圆片实际分组，用同一个例子记录余数、寻找答案。这样就能看清：有些条件能同时满足，有些条件却互相冲突。
完整的一组与剩下的几个
先取 个圆片。每 个装成一组，可以装满 组，还剩 个。满组里有 个，再加剩下的 个，回到原来的 个。剩下的数量叫作余数。
为什么余数一定小于每组数量？如果还剩 个，就能再装满一组，不能说分组已经结束。因此，除以 的余数只能是 。余数是 时，表示恰好分完。
下面每个实线框是一整组，虚线框是剩下的圆片。改变总数，再把每组数量从 换成 ；总数不会因为换分组方法而改变。绿色圆片在完整组里，金色圆片是余数。
现在用 表示待找的整数，用 表示完整组数。“除以 余 ”就写成 。因为我们只研究整个圆片的数目，这里的 和 都是整数。
同时满足两份记录
第一份记录要求总数除以 余 。从 开始，每次多加一整组 ，余数不变，于是得到 。这些数都满足第一份记录；非负的其他数不满足，因为除去余下的两个后，必须正好是整组的 。
第二份记录要求除以 余 。同样，从 开始，每次多加 ，得到 。我们要找的是同时出现在两列里的数，而不是把两个余数直接相加。
下面每次检查第一列中的一个候选总数，并把同一个数按 分组。两行上下对齐的数字表示同一个总数；实心标记表示满足该行的要求。候选数按 、、 的顺序检查。
找到 以后，要放回两份记录核对：，又有 。所以 确实满足。可是，还有没有别的答案？我们接着解释怎样把所有可能都照顾到。
同一列在两行里表示同一个总数。实心圆表示符合该行要求，高亮列是当前候选数。小屏幕可以横向滚动
| 总数 | |||||||||||||||
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| 除以 余 | · | · | ● | · | · | ● | · | · | ● | · | · | ● | · | · | ● |
| 除以 余 | · | · | · | ● | · | · | · | · | ● | · | · | · | · | ● | · |
| 候选数 | 除以 5 的余数 | 两条都满足？ |
|---|---|---|
| 2 | 2 | 否 |
为什么只需检查一段
在任何一个总数上加 ，相当于多了 组的 ，也相当于多了 组的 ，因为 。两种分法都只是增加完整组，余数都不改变。减去 也同样保留余数。
任意整数都能除以 ，写成 ，其中 。这里 是整数， 是余数。例如 ，而 。所以每个整数都能通过加减若干个 ，落到 至 中的一个数。
因此只要检查 到 ，就不会漏掉任何一类答案。其中满足第一份记录的只有 ；它们除以 的余数依次是 ，只有 的余数是 。这给出全部整数解 ，其中 可以是任意整数。
如果我们回到圆片总数这个问题，总数不能为负，所以只保留 。若只问整数，两侧的 都属于同一族答案。
为了把余数记录写短一些，我们引入记号 ，读作“ 模 同余于 ”。在这里它恰好表示除以 余 ，也就是说 是 的整数倍。“模数”就是这里分组所用的 。
先准备一个整数工具
刚才已经完整解决了 和 的例子。但为什么把它们换成另外两个数后，有时总能找到答案，有时找不到？我们需要知道，两种完整组有没有共同的大小。
一个正整数如果能整除两个数，就叫它们的公因数。也就是说，这两个数分别等于它乘以某个整数，没有余数。最大的那个叫最大公因数，记作 。例如 和 的公因数是 ，最大的为 ； 和 只有公因数 ，这种情况叫互质。
怎样找到最大公因数，并把它与原来的两个数联系起来？先做带余除法 。若一个数整除 ，它也整除 。反过来，若它整除 ，它也整除 。所以数对 和 的公因数完全一样。
我们可以不断把较大的问题换成“除数和余数”。正余数每次严格变小，最终一定遇到余数 。任何正整数都整除 ，所以最后一对数的最大公因数就是其中那个非零数；它可能是前一步的余数，也可能就是最初的除数。例如 ，最后一对是 ，答案为 。每次替换又保留了公因数，因此这个非零数也是原来两数的最大公因数。这个过程叫辗转相除法。
下面保留 、 两个原数，每次把新余数写成“原数乘以整数，再相加”。第一行只是 ；这样也能从较小的数开始，之后每一步仍然成立。
原来的两个数 3 和 5 始终保留。每一步把当前数对换成除数与余数
| 带余除法 | 用两个原数写出余数 |
|---|
沿着余数，回到它来自哪里
得到余数 的那次除法告诉我们 。前一次又告诉我们 。把这个 换成它的来源，再把括号前的负号分配进去，合并两份 ：
这样的回代总能进行，因为每个余数都等于前面的被除数，减去除数的一个整数倍。继续替换前面的余数，最终只会留下最初两个数。整数相加、相减、相乘仍是整数，所以系数始终是整数。因此，对任意正整数 ，总能把最大公因数写成 ，其中 为某两个整数。
推出中国剩余定理
现在把刚才的工具用到任意两个互质的正模数 。它们的最大公因数是 ，所以辗转相除并回代后，能找到整数 ，使 。 是刚才那种组合的两个系数，可以是负数。
我们希望一个整数 除以 余 ，除以 余 ，其中 、。先保证第一条：设 ，其中整数 还没有决定。这样，无论怎样选 ， 都是 的整数倍。
第二条需要 是 的整数倍。因此，我们希望让 与 的差能够被 整除。把已知的 乘以 ，就能造出这样的差：
现在选 。代回上一行，得到 ，右边是 的整数倍。因此 同时满足两份记录。这证明了答案一定存在，而不只是列出了一些成功例子。
接下来检查答案能有几类。假设 都满足两条记录，那么 同时是 、 的整数倍。先写成 。现在知道 被 整除，我们要证明 也被 整除，不能直接把 擦掉。
仍然用 ，两边乘以 得 。第一项是 的整数倍，因为 是；第二项也是，因为它有因数 。两项相加仍是 的整数倍，所以 ，其中 是整数。因此 。
所以任意两个答案只相差 的整数倍；反过来，给一个答案加上 的整数倍，也不改变任何余数。把已找到的答案除以 ，取余数 ，就得到区间 内唯一的答案；全部答案是 。这就是两个互质模数的中国剩余定理。
回到圆片问题，逐步代入
有共同因数时怎么办
如果模数不是互质的，会怎样？例如除以 余 的数都是奇数；除以 余 的数都是偶数。同一个整数不可能同时是奇数和偶数，所以这两份记录互相冲突。共同因数 正是冲突发生的地方。
设两个模数的最大公因数为 。如果有共同答案，写成 。移项得到 。因为 整除 ，右边每项都是 的整数倍，所以 必须被 整除。这是必要条件。
这个条件也足够。辗转相除给出 。若 ，两边乘以整数 ，得到 。取 ，它与 相差 的整数倍，与 相差 ，也是 的整数倍，所以两条都满足。
最后找出准确的重复间隔。把共同部分提出，写 、。 必须互质：若它们还有大于 的共同因数 ，原来的 就会有更大的共同因数 ，与 是最大公因数矛盾。
两个答案的差是 的倍数，写成 ；它也是 的倍数，所以 是 的倍数。因为 互质，上一章已证明的消去理由给出 是 的倍数。于是两个答案的差一定是 的倍数。
本身同时是 和 的倍数，而且上面的理由表明任意共同倍数都必须是它的倍数。因此，它就是最小公倍数，记作 。有解时，全部解每隔这个数重复一次。
下面你可以改变模数和余数。两个余数的差能否被最大公因数整除，决定了是否可能有解。你也可以逐个检查候选数，核对这个判断。表里列出了一个完整重复区间内、满足第一份记录的所有候选数，因此走完后就完成了这一组条件的检查。
这里 表示重复间隔。在 内，满足第一条的候选数共有 个，每两个相邻候选数相差 。
差 能被 整除，所以有解。全部答案为 ，其中 是整数。逐个检查候选数，就能在这一段找到它的代表。
再合并一条记录与练习
两条记录合并后，得到的是另一条余数记录。例如刚才的 ，可以写成 。如果还要求除以 余 ，我们就把新记录与这条合并后的记录继续配对。
先看 ，它们除以 的余数依次为 ，所以这次选出 。因为 与 互质，新的重复间隔是 ，得到 。核对原来的三条：，，。
对更多条记录，我们可以重复这个合并过程。每一步先检查当前两个模数的最大公因数条件；如果不兼容，就没有同时满足全部记录的整数。如果兼容，合并后的记录保留前面全部条件，再接下一条即可。
如果最初的模数两两互质，每次合并也会保持互质。理由可以用已证明的消去规则看出：若某个数 同时与 、 互质，就能分别写出 、；相乘后得到 ，所以 与 的任何公因数都必须整除 。逐次使用，就得到更多互质模数版本的中国剩余定理。
除以 余 ，除以 余 ，全部整数解是什么？
一个周期是 。在 到 中，第一条给出 ；除以 的余数分别是 。只有 满足第二条，因此 ，其中 为任意整数。代回：。
除以 余 ，除以 余 ，为什么这次可以？
最大公因数是 ，余数差 能被它整除，因此兼容。一个周期是 。候选 除以 的余数为 ，选出 。所以全部整数解为 ；例如 。
除以 余 ，除以 余 ，为什么不能把乘积 加上去解决冲突？
余数差 不能被最大公因数 整除，所以不存在起始答案。加 只会保留原有余数，不能把错误的余数变成要求的余数。
如果已经找到 ，又要求除以 余 ，会怎样？
合并后的数除以 都余 ，因为 ，而 是 的倍数。新条件要求余 ，于是冲突。用一般条件也得到同样判断：，而 不是 的整数倍。
