中国剩余定理

零、概述

本文介绍中国剩余定理以及其简单应用，阅读前请先了解《数论基础》

一、从问题入手

有物不知其数，三三数之剩二，五五数之剩三，七七数之剩二。问物几何？即，一个整数除以三余二，除以五余三，除以七余二，求这个整数。

《孙子算经》中首次提到了同余方程组问题，以及以上具体问题的解法，因此在中文数学文献中也会将中国剩余定理称为孙子定理。

二、数学语言表达

实际上，中国剩余定理的内容可以表达为如下：
对于同余方程组

$$\begin{cases} x \equiv a_1(mod \quad m1)\\ x \equiv a_2(mod \quad m2)\\ \quad \vdots\\ x \equiv a_n(mod \quad m_n) \end{cases}$$

其中$m_1,m_2,\cdots,m_n$互质,该方程的解为

$$x \equiv \sum_{i=1}^{n}{a_i*M_i*inv(M_i)} \quad (mod\quad M)$$

其中$M=\prod_{i=1}^nm_i$,$M_i=\frac{M}{m_i}$
该结论正确性容易证明，直接代入方程即可证明，接下来讨论的是如何使用简单的方法推出中国剩余定理。

三、从一个简单例子引入

一个数模以3得2，模以5得3，这个数是多少？

可能会有点复杂，我们先考虑一以下两个问题

一个数模以3得1，模以5得0，这个数是多少？
一个数模以3得0，模以5得1，这个数是多少？

好像很容易，第一个问题是10，第二个问题是6。用数学语言表达就是

$$\begin{cases} 10\equiv 1 (mod\quad 3)\\ 10\equiv 0 (mod\quad 5) \end{cases}\\ \begin{cases} 6\equiv 0 (mod\quad 3)\\ 6\equiv 1 (mod\quad 5) \end{cases}$$

由于同余式的乘法封闭性，我们可以将第一个方程组乘以2，将第二个方程组乘以3，那么结果为：

$$\begin{cases} 20\equiv 2 (mod\quad 3)\\ 20\equiv 0 (mod\quad 5) \end{cases} \\ \begin{cases} 18\equiv 0 (mod\quad 3)\\ 18\equiv 3 (mod\quad 5) \end{cases}$$

再由加法封闭性，将上下两个方程相加

$$\begin{cases} 38\equiv 2 (mod\quad 3)\\ 38\equiv 3 (mod\quad 5) \end{cases}$$

检查一下，38是不是满足原问题的条件？
不难发现，同余方程有类似向量的线性性质，这启发我们可以通过线性的变换来计算出特定同余方程的解。其中最简便的方法，便是计算出满足条件的一组基向量，然后直接线性相加得出结果。
同时，我们希望基向量是正交且标准化的的，也就是说，基向量有形如$(1,0,0,0,\dots)$的形式，如何求出满足这样的同余式？乘法逆元就派上了用场。

四、求出基向量

要想得到形如

$$\begin{cases} x\equiv 0 (mod\quad 2)\\ x\equiv 1 (mod\quad 3)\\ x\equiv 0 (mod\quad 7)\\ \end{cases}$$

的同余方程，首先要除第二个同余方程以外的通余方程右边为0，我们可以直接计算出剩余项的lcm,由于$m_i$互质，则可以知道14的倍数都是满足条件的。其次我们希望x与1在模3意义下同余，可以通过枚举来测试，但是最好的方法是使用乘法逆元。
显然，有如下同余方程：

$$14\equiv14\pmod{3}$$

左右同乘以14在模3意义下的乘法逆元，则有

$$14*inv(14)\equiv 1\pmod{3}$$

这样，我们便求出了其中的一个基向量。
将结论推广到更一般的形式，对于同余方程组

$$\begin{cases} x \equiv a_1(mod \quad m1)\\ x \equiv a_2(mod \quad m2)\\ \quad \vdots\\ x \equiv a_n(mod \quad m_n) \end{cases}$$

其第$i$个基向量为

$$e_i=M_i*inv(M_i)$$

其中$M_i$是除$m_i$以外的所有$m$的乘积。

• 为什么是“除$m_i$以外所有m的乘积”？

  “所有m的乘积”是为了保证求出的这个基向量在其他模意义下均与0同余，以免影响其他模意义下的基向量的结果。

• 如何理解基向量

  这里的基向量可以仅仅将其理解成一个值，这个值在当前模意义下与1同余，在其他模意义下是0，只要将各个模意义下的基向量线性组合，就可以得到x的最终解。

所以，最终的答案便是

$${ \left( \begin{array}{ccc} a_1,& a_2,& \cdots,& a_n \end{array} \right) }* { \left( \begin{array}{c} e_1\\ e_2\\ \vdots\\ e_n \end{array} \right)}$$

也即

$$x \equiv \sum_{i=1}^{n}{a_i*M_i*inv(M_i)} \quad (mod\quad M)$$

如何与线性代数类比

求同余方程的过程可以看成是，求出一个向量，该向量在$m_i$所在维度上长度为$a_i$，我们要做的就是求出$m_i$维度上的单位向量（且该向量在其他维度投影为0），然后用线性性质将其相加。
该部分关于向量等等的表述可能存在一些问题，感性理解一下吧