引言
中国剩余定理用于高效求解一元同余方程组，基本所有标准数论书都会讲解。之所以本博客还有存在的价值，是因为本人认为学习一个定理的最好方式是重新发现该定理。还有，在教学过程中，学生们总问，“为什么数学家们会想到这样的定理”，诸如此类的问题。我试图展示，即使是非常著名的大定理可能也只是源自于正常的思路，并不神秘。以下内容试图达到以上两个小目标，如果读者能从中找到一点乐趣就善莫大焉咯。
阅读本文的基础包括：模算术运算、同余理论、费尔马小定理、欧拉定理以及扩展欧几里得算法。也许阅读本文只需要一点点时间，不大好估计，因为实在是很简单。
求解一元同余方程组
先看求解一元同余方程组的实例，假定需要解以下方程组： \[\begin{eqnarray*} x &\equiv& 2 \pmod{5} \\ x &\equiv& 3 \pmod{7} \end{eqnarray*}\]
有一种平凡的解决方法如下：
从一个同余式中得到\(x = 5t + 2\)，\(t \in \mathbb{N}\)；
把\(x\)代入第二个同余式得到：$ 5t + 2 $；
整理可得：\(5t \equiv 1 \pmod{7}\)；
上式两边同乘\(5^{-1}\)得到\(t = 7s + 3\)，\(s \in \mathbb{N}\)；
最后，\(x = 35s + 17\)，即\(x \equiv 17 \pmod{35}\)。
以上例子告诉我们，解同余方程组是非常简单的工作。然而，从算法的角度看，这不是一种好的解法。中国剩余定理给出了一种简洁、高效的解决方案。
中国剩余定理--数论角度
对任意的一元同余方程组，中国剩余定理（Chinese Remainder Theorem，简记为CRT）， 告诉我们，对特定的模数总是有唯一解，并给出了一种高效的求解方法。先看以下定理的描述。
中国剩余定理
设\(p\)和\(q\)是互素的两个正整数，\(n = pq\)。对任意的\(a \in \mathbb{Z}_p\)和\(b \in \mathbb{Z}_q\)，存在 唯一解\(x\)，\(0 \leq x < n\)使得： \[\begin{eqnarray*} x &\equiv& a \pmod{p}\\ x &\equiv& b \pmod{q}\end{eqnarray*} \]
然而，在给出整个定理证明之前，让我们试图重新“发明”这个定理的证明。希望在这一节当中，读者可以享受到发明定理的乐趣，这比读懂一个证明要快乐得多。所以，在我提示大家要停下来思考的时候，请尽量跟我的节奏走。
我们的任务是解以上两个同余方程，让我们先考察其中一个同余式。比如，设\(p\)为一个整数，对任意的\(a \in \mathbb{Z}_p\)， 所要求解的\(x\)要满足方程 \[x \equiv a \pmod{p}\] 那么，\(x\)应该长什么模样？答案之一，当然是存在\(k\in \mathbb{Z}\)，使得\(x = a +kp\)。这是之前例子的方法。还有没有其他答案？
其实，求解\(x\)是要问，给定\(a\)和\(p\)，在模\(p\)的情况下，什么数会与\(a\)同余？或者说，试图找一个值\(a'\)，使得 \[ a a' \equiv a \pmod{p}\] 第一印象应该是选一个模\(p\)等于\(1\)的数\(a'\)，当然\(a'\)不能简单地等于1。
大家能回顾一下线性代数中相似矩阵的定义吗？对两个\(n\times n\)矩阵\(A\)和\(B\)，如果存在一个可逆的\(n\times n\)矩阵\(C\)使得： \[A = C^{-1}BC\] 则称\(A\)和\(B\)为相似矩阵。回到同余式\(x \equiv a \pmod{p}\)，我们能发现\(x\)与\(a\)是相似数吗？建议读者在此处暂停阅读，自己思考一段时间。
继续刚才的问题，对于整数\(a\)，在可逆矩阵的启发下，对应的可逆数（与相似矩阵的可逆矩阵对应）难道不应该是模\(p\)下互为乘法逆元的整数\(c\)和\(c^{-1}\)吗？也就是说，对任意的\(c\in \mathbb{N}\)，如果\(gcd(c,p)=1\)，则存在唯一乘法逆元\(c^{-1}\in \mathbb{N}\)，使得\(c c^{-1} \equiv 1 \pmod{p}\)。如果\(x = c c^{-1} a\)，称整数\(x\)和\(a\)相似。为什么相似，因为\(x\)和\(a\)模\(p\)同余，且不等。注意，给定\(a\)，可以构造多个不同的\(x\)与之相似。
对于满足两个同余式\(x \equiv a \pmod{p}\)和\(x \equiv b \pmod{q}\)的解\(x\)，大致形式应该是既与\(a\)相似又与\(b\)相似。 分别相似并不难构造，难点是同时满足相似性。比如令\(x = c_1 c_1^{-1}a + c_2c_2^{-1}b\)，其中\(c_1 c_1^{-1} \equiv 1 \pmod{p}\)， \(c_2 c_2^{-1} \equiv 1 \pmod{q}\)。现在\(x\)模\(p\)会得到\(a\)，但是$ c_2 c_2^{-1} b$多出来的部分不知道是什么，不大可能是\(0\)。\(x\)模\(q\)会得到\(b\)， 但是又多出了\(c_1 c_1^{-1}a\)。怎么解决？也就是说，在模\(p\)（或者模\(q\)）的同时要使那些讨厌的部分消失。怎么能做到？ 建议读者在此处暂停阅读，自己思考一段时间。
相信答案并不难得到。如果把\(c_2c_2^{-1}b\)这一项中的\(c_2\)人为设置为\(p\)，在模\(p\)的时候，这一项就被消去了。 同理，把\(c_1c_1^{-1}a\)这一项中的\(c_1\)人为设置为\(q\)即可。这也大致解释了，为什么定理的条件需要\(p\)与\(q\)互素。 如果你想出来了，恭喜你，请看以下证明。以下定理与证明都是教科书式的东西，如果懂了可以跳过，没有什么特别的内容。
中国剩余定理的证明
使用构造法。因为\(p\)与\(q\)互素，则存在\(p^{-1}\)和\(q^{-1}\) 分别使得\(p p^{-1} \equiv 1 \pmod{q}\)和\(qq^{-1} \equiv 1 \pmod{p}\)。 令整数\(x\)为： \[ x = a q q^{-1} + b p p^{-1} \] 容易验证，\(x\)同时满足两个同余式。最后需要证明在模\(n = pq\)情况下，\(x\)是唯一解。即需要证明如果存另一个解，它也必然与\(x\)模\(n\)同余。假设\(\exists y \neq x\)是另一个解，则存在\(t \in \mathbb{N}\)使得\((y - x ) = tp\)。此时是把\(x\)和\(y\)理解为\(a + kp\)的形式。类似，如果把\(x\)和\(y\)理解为\(b + kq\)的形式，则存在\(s \in \mathbb{N}\)使得\((y - x ) = sq\)。因为\(p\)与\(q\)互素，则存在某个\(k \in \mathbb{N}\)，使得\((y - x) = kpq\)。因此，\(y \equiv x \pmod{n}\)。证完！
中国剩余定理--推广版
设\(m_1, m_2, \cdots, m_n\)是两两互素的整数，对以下\(n\)个同余式的同余方程组 \[\begin{eqnarray*} x &\equiv& a_1 \pmod{m_1}\\ &\cdots& \\ x &\equiv& a_n \pmod{m_n}\end{eqnarray*}\] 存在模\(M\)的唯一解，其中\(M = m_1 m_2 \cdots m_n\)。
中国剩余定理--推广版的证明
构造法。令\(M= \prod_{i = 1}^{n} m_i\)，记\(b_i = M/m_i\)。 存在\(b_i ^{-1}\)使得\(b_i b_i ^{-1} \equiv 1 \pmod{m_i}\)。则 \[x = \sum_{i=1}^{n} a_i b_i b_i^{-1}\pmod{M}\] 是方程组的唯一解。
斌头剩余定理
本博客有意思的部分开始了！或者也可以说是最没意思的部分，因为以下内容不会出现在标准教科书当中。稍微把中国剩余定理的要求增强一点点，要求同余方程组的模数分别是不同的素数，然后可以继续大开脑洞，请跟上思路。
在证明中国剩余定理的时候我们问：给定\(a\)和\(p\)，找一个值\(a'\)，使得 \[ a a' \equiv a \pmod{p}\] 利用乘法逆元构造一个\(1\)并不是唯一选择。费尔马小定理告诉我们，如果\(p\)是素数，存在\(c\in \mathbb{Z}\)且\(gcd(c,p)=1\)使得： \[ c^{p-1} \equiv 1 \pmod{p}\] 所以，使用某个数\(b\)的\(p-1\)次方也能构造出一个\(a\)的相似数。那么，构造出来的\(x\)大致可以是这个形式： \[a c_1^{p-1} + bc_2^{q-1}\] 请问，\(c_1\)和\(c_2\)分别选择什么可以使得同余方程组得到满足呢？
有了以上的经验，答案很容易想到：分别取\(q\)和\(p\)即可。于是我们很可能会得到一个斌头剩余定理。
斌头剩余定理--初始化版本
设\(p\)和\(q\)是不等的两个素数，\(n = pq\)。对任意的\(a \in \mathbb{Z}_p\)和\(b \in \mathbb{Z}_q\)，存在 唯一解\(x\)，\(0 \leq x < n\)使得： \[\begin{eqnarray*}x &\equiv& a \pmod{p}\\ x &\equiv& b \pmod{q}\end{eqnarray*}\] 且\(x = (a q^{p-1} + b p^{q-1}) \bmod{n}\)。
请验证该定理是否成立？对了，这里唯一性还需要证明吗？不需要，唯一性与\(x\)的构造无关。
故事还没有完，因为以上假设\(p\)和\(q\)是不等的两个素数，这要求比中国剩余定理还差一步的距离。如果使用中国剩余定理的标准设定，设\(p\)和\(q\)是不等的且互素的整数，斌头剩余定理就失败了！怎么挽救呢？费尔马小定理是什么定理的特例？欧拉定理！哇哦，欧拉挽救了斌头。欧拉定理说的是，如果\(gcd(p,q)= 1\)，则：
\[q^{\phi(p)} \equiv 1 \pmod{p}\]
\(\phi\)是欧拉函数。所以，相似数的构造可以使用欧拉定理这个\(1\)。
斌头剩余定理--最终版
设\(p\)和\(q\)是不等的且互素的整数，\(n = pq\)。对任意的\(a \in \mathbb{Z}_p\)和\(b \in \mathbb{Z}_q\)，存在 唯一解\(x\)，\(0 \leq x < n\)使得： \[\begin{eqnarray*}x &\equiv& a \pmod{p}\\ x &\equiv& b \pmod{q}\end{eqnarray*}\] 且\(x = (a q^{\phi(p)} + b p^{\phi(q)}) \bmod{n}\)。
请读者论证
斌头剩余定理是正确的。请编程实现相关算法并计算。
斌头剩余定理实在是没有用处的定理。请说明理由。
斌头剩余定理能有效帮助大家记忆中国剩余定理，无需理由！
中国剩余定理--抽象代数的角度
中国剩余定理是一种高效的工具，在特定的时候，它也是一种抽象的表达，是从代数的角度认识某些数字系统的方法。在很多情况下，当我们说“哦，这是中国剩余定理!”的时候，我们并不一定在说“这里有一种高效的计算方法”，而往往是说“这类数值可看为具有这样的形式”。从抽象代数的角度去看CRT，就是学习如何把CRT看为一种“语言”。为避免本文过长，就留待以后再说了。
总结
中华文化源远流长，其中孙子定理又称中国剩余定理是这种文化里的一颗闪亮的明星。中国剩余定理与中国的关系就好比超奇异椭圆曲线与奇异的关系一样密切。中国剩余定理是中国的！
懂中国剩余定理的人实在很多，但是懂斌头剩余定理的就不见诸科技文献报道，颇为可惜，哈哈哈，于是就有了这篇博客。正如博客里面已经论述，斌头剩余定理实在是没有用处的定理。在此只能道歉，“老师教了一堆没用的东西”这句话在此有效。学习嘛，无非就是发现乐趣，没用就没用吧。
