中国剩余定理证明(需要前置知识：逆元、线性同余方程)

中国剩余定理对于一元线性同余方程组的求解

中国剩余定理的提出：

最早于中国南北朝时期（公元5世纪）的数学著作《孙子算经》提出，故又称孙子定理。

记载原文如下： “ 有物不知其数，三三数之剩二，五五数之剩三，七七数之剩二。”

意思是：有一个整数，除以3余2，除以5余3，除以7余2，求这个数是多少？

写成线性同余方程组：

$$\{\begin{array}{l}x\equiv 2(mod3)\\ x\equiv 3(mod5)\\ x\equiv 2(mod7)\end{array}$$

什么是同余?

同余在数学中是指数论中的一种等价关系，符号为$\equiv$。

指当两个整数$a,b$除以同一个正整数$m$，若得相同余数$r$，则称这两个整数$a,b$对于模$m$​同余。

记作 $a\equiv b(modm)$，读作$a$与$b$关于模$m$​同余。

什么是线性同余方程？

在数论中，线性同余方程是最基本的同余方程，“线性”表示方程的未知数次数是一次。

即形如：$ax\equiv b(modm)$​​ 的方程。

求解关于x的线性同余方程组：

构造$x=2r_1+3r_2+2r_3$。

$r_1,r_2,r_3$需要满足下列条件：

$For{r}_1$：
$$\{\begin{array}{l}{r}_1\equiv 1(mod3)\\ r_1\equiv 0(mod5)\\ r_1\equiv 0(mod7)\end{array}$$
$For{r}_2$
$$\{\begin{array}{l}{r}_2\equiv 0(mod3)\\ r_2\equiv 1(mod5)\\ r_2\equiv 0(mod7)\end{array}$$
$Forr3$​
$$\{\begin{array}{l}{r}_3\equiv 0(mod3)\\ r_3\equiv 0(mod5)\\ r_3\equiv 1(mod7)\end{array}$$

定义**$[a^{-1}{]}_b$表示$a$​在模$b$意义下的乘法逆元。**

什么是乘法逆元？

乘法逆元可以理解为倒数。在数学中，与$x$相乘得$1$的数，即为数 𝑥 的倒数/乘法逆元，记作$\frac{1}{x}$或$x^{-1}$。​

什么是模意义下的乘法逆元？

在线性同余方程中$a,x,n$满足：$ax\equiv 1(modm)$ 就称 $x$是$a$在模$m$的意义下的乘法逆元，读作$amodm$的逆元，记作$[a^{-1}{]}_m$。​

逆元的求解一般用：

1. 扩展欧几里得。
2. 费马小定理。
3. 线性求逆元。

这里由于篇幅问题就不过多描述。

$\because r_1$ 是 $5$ 的倍数 , $r_1$是$7$的倍数

$\therefore r_1=35k_1,k_1\in \mathbb{Z}$

$\because r_1\equiv 1(mod3)$

$\therefore r_1$既是$35$的倍数，又模$3$余$1$，$k_1$是$r_{1}mod3$ 的逆元

$\therefore k_1=[35^{-1}{]}_3=2+3t_1(t_1\in \mathbb{Z})$

$\therefore r_1=35\ast k_1=70+105t_1$

同理可以解出$r_2,r_3$
$$\{\begin{array}{l}{r}_1=35\ast [35^{-1}{]}_3=70+105t_1\\ r_2=21\ast [21^{-1}{]}_5=21+105t_2\\ r_3=15\ast [15^{-1}{]}_7=15+105t_3\end{array}$$
代回$x=2r_1+3r_2+2r_3$，得到：

$x=140+6t_1+63+15t_2+30+14t_3$ $=233+105(t_1+t_2+t_3)$

$\because t_1,t_2,t_3$是任意的非负整数。

$x=233+105t(t\in \mathbb{Z})$

所以这个问题的最小正整数解为$x=23$​​。

这样的构造就是中国剩余定理求解的过程。

中国剩余定理求解通解：

对于一个一元的线性同余方程组：
$$\{\begin{array}{l}x\equiv a_1(mod{m}_1)\cdot \cdot \cdot \cdot (1)\\ x\equiv a_2(mod{m}_2)\cdot \cdot \cdot \cdot (2)\\ ...\\ x\equiv a_n(mod{m}_n)\cdot \cdot \cdot \cdot (n)\end{array}$$
（为了方便表述，这里给每个同余方程编号$1,2,...,i$）

其中任意两个$m_i$之间互质。

对于第$i$个同余方程：我们需要构造出这样的一个数$r_i$

使得$r_i$​满足：
$$\{\begin{array}{l}{r}_i\equiv 0(mod{m}_1)\cdot \cdot \cdot \cdot (1)\\ r_i\equiv 0(mod{m}_2)\cdot \cdot \cdot \cdot (2)\\ ...\\ r_i\equiv 1(mod{m}_i)\cdot \cdot \cdot \cdot (i)\\ r_i\equiv 0(mod{m}_n)\cdot \cdot \cdot \cdot (n)\end{array}$$
通过上面的求解过程，我们可以给出构造的过程：

设$M$表示${\prod }_{i=1}^n{m}_i$，$M_i=\frac{M}{m_i}$​

设 $t$ 表示$M_i$在模$a_i$意义下的最小正整数逆元。

得到 $r_i=M_i\ast t_i+k\ast M$

$\because x={\sum }_{i=1}^n(a_i\ast r_i)+kM$

$\therefore x={\sum }_{i=1}^n(a_i\ast M_i\ast t_i)+kM(k\in \mathbb{N})$

局限：

中国剩余定理并不适用于所有的一元线性同余方程，它只适用于模数均互质的情况。

对于模数不互质的情况，我们需要深入学习 拓展中国剩余定理$EXCRT$​

由于篇幅问题，本文章不进行讲解。