中国剩余定理的证明-中国剩余定理证明

中国剩余定理（中国余数定理）在数学史里是个大命题，古时候中国数学家早就琢磨透了如何用中国剩余定理。
这玩意儿实际上就是把大难题拆成小难题，再拼回去。咱们拿个例子看看，比如要解这个方程：$x equiv 2 pmod 3$，$x equiv 3 pmod 5$，还有 $x equiv 2 pmod 7$。乍一看，这三个条件像三颗钉子，要把一根铁钉钉进去，显得挺别扭。但换个角度看，$3$、$5$、$7$ 这三个数叫互质数，它们之间互不买账，互没有公因数。
这时候就能够把三个难题变成三个彻底独立的子难题。 先看第一个子难题。已知 $x equiv 2 pmod 3$，说明 $x$ 除以 $3$ 除出去剩 $2$。
这时候能够写 $x$ 的表达式，$x$ 肯定是 $3$ 的倍数加 $2$，也就是 $3k + 2$ 这种形式。
这相当于说 $x$ 在模 $3$ 的余数世界里，只有一种可能，就是那个被标记为 $2$ 的格子里的数。 再看第二个子难题。已知 $x equiv 3 pmod 5$，说明 $x$ 除以 $5$ 除出去剩 $3$。
这就意味着 $x$ 等于 $5$ 的倍数加 $3$，也就是 $5j + 3$。同样的道理，这就把 $x$ 的取值范围给压扁了，只剩下一个模 $5$ 的余数。 接着看第三个子难题。已知 $x equiv 2 pmod 7$，说明 $x$ 除以 $7$ 除出去剩 $2$。
那 $x$ 就是 $7$ 的倍数加 $2$，也就是 $7m + 2$。 目前把这三个条件拼起来。$x$ 务必既是 $3k+2$，又是 $5j+3$，还得是 $7m+2$。
这就好比你挑衣服，既得穿带红领口的（模 $3$），又得穿背号 $3$ 的（模 $5$），还得穿号码 $2$ 的（模 $7$）。
这时候最费事的点来了，就是要把所有可能的 $k, j, m$ 组合找出来，看看有没有共同的项。
不过出于三个系数互质，这玩意儿实际上挺好办，不用去遍历所有整数，直接取模乘积就行。 这就引出了个关键公式。在模 $M = 3 times 5 times 7 = 105$ 的范围内，知足这三个条件的数 $x$ 都是 $105$ 的倍数加上某个特定的数。
这个特定的数如何算？我们需求算出 $105$ 的逆元。出于 $3, 5, 7$ 互质，故此 $105$ 和 $105$ 互质，这就是中国剩余定理的核心——存有唯一解。 我们来算算这个特定的数。先算 $3$ 和 $5$ 乘积 $15$ 在模 $7$ 里的逆元。也就是求 $15k equiv 1 pmod 7$，简化一下就是 $1k equiv 1 pmod 7$，故此 $k=1$。
这说明 $3 times 5 = 15 equiv 1 pmod 7$。 接下来算 $7$ 和 $15$ 乘积 $105$ 在模 $3$ 里的逆元。$105$ 是 $3$ 的倍数，故此 $105 equiv 0 pmod 3$，这就费事了，没法直接除。换个思路，我们要算的是 $A cdot 7 cdot 5 cdot 2 pmod 3$ 吗？不对，公式推导略微绕点。准来说，我们需求计算 $x = a_1 m_1 + a_2 m_2 + a_3 m_3$。 这里 $a_1=2, m_1=3$；$a_2=3, m_2=5$；$a_3=2, m_3=7$。公式里项是 $2 times 3 times k times (3^{-1} bmod 5)$ 这种。先算 $3$ 在模 $5$ 的逆元。$3 times 2 = 6 equiv 1 pmod 5$，故此逆元是 $2$。 再算 $5$ 在模 $3$ 的逆元。$5 times 2 = 10 equiv 1 pmod 3$，故此逆元是 $2$。 最终算 $7$ 在模 $3$ 的逆元。$7 equiv 1 pmod 3$，逆元就是 $1$。 把这些乘起来：$x = 2 times (3 times 2) + 3 times (5 times 2) + 2 times (7 times 1)$。 等一下，这里的权重搞反了。标准形式是 $x = sum a_i (prod_{j ne i} m_j) cdot (m_i^{-1})$。 第一项：$a_1 cdot m_2 cdot m_3 cdot (m_1^{-1}) = 2 cdot 5 cdot 7 cdot (3^{-1} bmod 5)$。$3^{-1} equiv 2$，故此 $70 cdot 2 = 140$。 第二项：$a_2 cdot m_1 cdot m_3 cdot (m_2^{-1}) = 3 cdot 3 cdot 7 cdot (5^{-1} bmod 3)$。$5 equiv 2 equiv -1 equiv 2^{-1} equiv 2$（出于 $2 times 2 = 4 equiv 1$），故此 $63 cdot 2 = 126$。 第三项：$a_3 cdot m_1 cdot m_2 cdot (m_3^{-1}) = 2 cdot 3 cdot 5 cdot (7^{-1} bmod 3)$。$7 equiv 1$，$1^{-1}=1$，故此 $30 cdot 1 = 30$。 加起来：$140 + 126 + 30 = 296$。 这个 $296$ 是不是我们要找的模 $105$ 的解？先算一下 $296 div 105$。$296 = 2 times 105 + 86$。
故此余数是 $86$。 验证一下：$86 div 3 = 28 dots 2$，对。$86 div 5 = 17 dots 1$，不对，刚刚算错了。 重新算第二项。$m_2^{-1} bmod 3$。$5 equiv 2 equiv -1$，逆元是 $-1 equiv 2$。$3 cdot 3 cdot 7 cdot 2 = 126$。$126 div 105 = 1 dots 21$。 第三项：$m_3^{-1} bmod 3$。$7 equiv 1$，逆元 $1$。$2 cdot 3 cdot 5 cdot 1 = 30$。 第一项：$m_1^{-1} bmod 5$。$3 equiv 3$，$3^{-1} equiv 2$。$2 cdot 5 cdot 7 cdot 2 = 140$。$140 div 105 = 1 dots 35$。 总数：$35 + 21 + 30 = 86$。 还是不对。
哪儿错了？公式里的乘积是不是搞反了？ 啊，公式里的 $m_i$ 应当是那个分母对应的模数，而 $a_i$ 是余数。 对的公式是：$x = sum_{i=1}^n a_i M_i^{-1} prod_{j ne i} M_j$。 第一项 $i=1$ ($a_1=2, M_1=3$)：$2 cdot (1/3) cdot (5 cdot 7) = 2 cdot 2 cdot 35 = 140$。 第二项 $i=2$ ($a_2=3, M_2=5$)：$3 cdot (1/5) cdot (3 cdot 7) = 3 cdot 2 cdot 21 = 126$。 第三项 $i=3$ ($a_3=2, M_3=7$)：$2 cdot (1/7) cdot (3 cdot 5) = 2 cdot 1 cdot 15 = 30$。 总和 $140+126+30=296$。 $296 pmod{105}$：$296 - 2 times 105 = 296 - 210 = 86$。 验证 $86 pmod 3 = 2$ (对)。$86 pmod 5 = 1$，不对，题目要求余 $3$。 哦，第二项里的 $M_2$ 是 $5$。$a_2/M_2 equiv 3/5 equiv 3 cdot 2 = 6 equiv 1$。$3 cdot 2 cdot 21 = 126$。$126 pmod 5 = 1$。 这说明我的逆元计算要么代入公式有难题。 $3 cdot 7 = 21$。$21 pmod 5 = 1$。$21^{-1} bmod 5$ 不存有，出于 $gcd(21,5)=1$，故此逆元存有。$21 times x equiv 1 pmod 5$。$21 equiv 1$，故此 $x=1$。 那第二项应当是 $3 cdot 3 cdot 7 cdot 1 = 63$。 $140 + 63 + 30 = 233$。 $233 div 105 = 2 dots 23$。 $23 pmod 3 = 2$。$23 pmod 5 = 3$。$23 pmod 7 = 2$。 对了！余数分别是 $2, 3, 2$。彻底符合题目条件。 刚刚算 $126$ 是出于当作 $21$ 的逆元是 $2$，实际上 $21 equiv 1$，故此逆元就是 $1$。 好啦，过程也摆平了。
既然 $x=23$ 知足条件，那在模 $105$ 的范围内，$23$ 就是唯一的解。
这就是中国剩余定理的威力。 再举个更生活化的例子吧。假设你是做数学题，既要保证你的年龄除以 $3$ 余 $1$，既要保证年龄除以 $4$ 余 $2$，又要保证年龄除以 $5$ 余 $3$。
这时候就能够用中国剩余定理把三个条件分开解了。先解除以 $3$ 余 $1$，拿到 $3k+1$。再解除以 $4$ 余 $2$，拿到 $4j+2$。再解除以 $5$ 余 $3$，拿到 $5m+3$。把这三条线画在数轴上，看它们有没有交点。出于 $3, 4, 5$ 互质，故此肯定有交点。
这个交点就是你的年龄。 这个方式之故此被广泛推崇，是出于它把一个大难题拆解成了小难题，再把小难题解决后又能塞回原来的大框架里。就像盖房子，先把地基打好，再把墙面砌好，最终把屋顶盖上去。地基是互质的，分工搭伙，缺一不可。 有时候我们会遇到类似的变体。
比如互质的数变多了，是 $13$ 个，$17$ 个，还是 $19$ 个？这时候算法就略微慢了点，出于要算 $19$ 次逆元，$13$ 次逆元。但总体思路不如何变。就是不断把大模数拆成小模数乘积，然后分别求每个小模数对应的系数，最终加起来。 这就有点像拼拼图。大模数像是整个拼图的大轮廓，小模数是每一块拼图。先算每一块拼图能拼出啥形状，再把形状拼起来，看看能不能组成整个的大轮廓。
要是大轮廓里的空缺没地方填，那就说明这组数互质了，能解出来。 在实际的高数课程里，老师间或会来问：“要是模数包含 $5$ 的平方，比如 $25$，还能不能用这个定理？”这时候就需求小心了。出于 $5$ 和 $5$ 不互质了，那个互质条件就失效了。
这时候就不能直接套公式了，得用欧几里得辗转相除法去化简，要么用更高级的扩张欧几里得算法来求新的系数。
这也是为啥书上有时候会唠叨几句，强调互质的关键性。 故此说，中国剩余定理实际上就是一个“化繁为简”的魔法。面对一堆复杂的同余方程，只要看到模数两两互质，脑子里就不怕了。先找规律，再找交点，最终发现个小小的整数。
这过程别看有点抽象，但本质就是代数结构的体现。 最终再想个细节。
比如模数是 $12$，余数是 $4$。
那 $12$ 和 $5$ 互质吗？不互质，gcd 是 $1$。能够。模数是 $8$，余数是 $1$。$8$ 和 $5$ 互质吗？不，gcd 是 $1$。能够。模数是 $6$，余数是 $3$。$6$ 和 $5$ 互质吗？gcd 是 $1$。能够。
可是模数 $2$ 和 $3$，余数 $1$，$1$。互质。模数 $3$ 和 $4$，余数 $2$，$2$。互质。 这里有个陷阱。
比如模数是 $8$，余数是 $2$。$8$ 和 $4$ 不互质。
这时候就不能直接用 $a cdot M_i^{-1}$ 这种形式了，出于 $M_i$ 会包含公因子，害得逆元不存有。
这就是为啥我们前面强调互质的缘由。
只有互质的时候，路径才清楚，解才是唯一的。 故此你看，数学这东西，有时候就是靠这些看似偶然的互质关系，把庞杂的约束条件一步步化解开。中国剩余定理就是那个愿意帮你拆解难题的数学家。它不要求你一启动就想通所有套路，只需求知道遇到互质数，就把大难题拆成小难题解决就行。
这种思维方式，在解决复杂系统的时候往往能用到极致。