引入

最早，在《孙子算经》中有这样一个问题：”今有物不知其数，三三数之剩二，五五数之剩三，七七数之剩二，问物几何？“

上面的问题可以转换为以下这样一个方程组：

$ \begin{cases}x\mod 3=2\ x\mod 5=3\ x\mod 7=2\end{cases} $

其中这个x就是我们要求的数。而中国剩余定理就是用来解决上述形式的方程组的x解的

在开始解答这个问题之前，我们先来了解一下几个数论基本知识

$ a\mod b=(a+k*b)\mod b $

$ a\equiv b(\mod c)\leftrightarrow a\mod c=b\mod c $

解答

在了解两个基本不等式之后我们就可以对上述方程组做一些变换了：

$ \begin{cases}x=k_13+2\ x=k_25+3\ x=k_3*7+2\end{cases} $

直接看上面的方程组，好像直接求解出$ k_1、k_2、k_3 $不太现实，所以我们需要另寻出路。在这里我们先假设三个数，分别是$ n_1、n_2、n_3 $，满足以下条件：

$ \begin{cases}n_1\mod 3=2\n_2\mod 5=3\n_3\mod 7=2\end{cases} $

假如$ n_2、n_3 $均能整除3的话，那么就有：

$ \begin{cases}n_2=k’_23\n_3=k’_33\end{cases} $

$ (n_1+k’_23+k’_33)\mod 3=n_1\mod 3=2 $

$ (n_1+n_2+n_3)\mod 3=2 $

那么我们继续假如$ n_1、n_3 $能被5整除，$ n_1、n_2 $能被7整除，那么就有：

$ \begin{cases}(n_1+n_2+n_3)\mod 3=2\(n_1+n_2+n_3)\mod 5=3\(n_1+n_2+n_3)\mod 7=2\end{cases} $

对比题目中的方程组，可以看出只要满足以下条件就能使我们需要解的$ x=(n_1+n_2+n_3) $：

1.$ n_1 $除以3余2，且是5和7的公倍数

2.$ n_2 $除以5余3，且是3和5的公倍数

3.$ n_3 $除以7余2，且是3和7的公倍数

我们只需要将$ n_1、n_2、n_3 $求出来后相加即可得我们相求的x值。不过，这只是其中一个解，并不是最小解。要求最小解我们还需要除以$ n_1、n_2、n_3 $的最小公倍数

这里以$ n_1 $求解为例，$ n_2、n_3 $求解过程类似

$ \begin{cases}n_1\mod 3=2\n_1=5k’_2\n_1=7k’_3\end{cases} $

由于$ gcd(35,3)=1 $，所以35存在模3下的逆元

现在要求$ n_1 $在模3下的逆元，根据贝祖定理，我们需要人为构造：

$ 70a+6b=2 $

由于$ gcd(70,6)=2 $，所以满足贝祖定理的条件，当且仅当c为$ gcd(a,b) $的倍数时，$ ax+by=c $有整数解

由扩展欧几里得算法可得：$ 2=70\times (-1)+6\times 12 $

$ a=-1\mod 3=2 $

所以$ n_1=70\times 2=140 $

同理可得：$ n_2=63,n_3=30 $

所以$ x=n_1+n_2+n_3=233 $

不过此时并不是最小数，我们还需要将$ 233\mod (3,5,7)_{最小公倍数105}=23 $

中国剩余定理可求解如下形式的一元线性同余方程组（其中$ n_1,n_2,\cdots,n_k $两两互质）

$ \begin{cases}x\equiv a_1(\mod n_1)\ x\equiv a_2(\mod n_2)\ \cdots\ x\equiv a_k(\mod n_k)\end{cases} $

1.计算所有模数的积n

2.对于第i个方程：

a.计算$ m_i=\frac{n}{n_i} $（是除了$ n_i $一外所有模数的最小公倍数）

b.计算$ m_i $在模$ n_i $下的逆元$ m^{-1}_i $

c.计算$ c_i=m_im_i^{-1} $

3.方程组在模n下的唯一解为（最小解）：$ x=\sum^{k}_{i=1} a_ic_i(\mod n) $

由于上文的引入和最后的定理来自不同文章，所以上下两部分关联性不强，有时间的话还会不上对于上文所展示的中国剩余定理公式的推导的

原文链接：
https://www.yuque.com/fragrantveget/ucxpnh/oms84fginr2e5o6l?singleDoc# 《中国剩余定理（Chinese Remainder Theorem，CRT）》