写在前面
上一节介绍了欧拉定理和欧拉函数并加以证明。其中欧拉函数是积性函数的证明用到了中国剩余定理【欧拉函数性质4】，没印象的可以再看看， 当时没有展开，本节详细说明下。
中国剩余定理
中国剩余定理(Chinese remainder theorem(CRT))，是中国古代求解一次同余式组的方法,是数论中一个重要定理。
最早于中国南北朝时期（公元5世纪）的数学著作《孙子算经》提出，故又称孙子定理。
记载原文如下：
”有物不知其数，三三数之剩二，五五数之剩三，七七数之剩二。问物几何？"
意思是，一个整数除以3余2，除以5余3，除以7余2，求这个整数.
类似的还有韩信点兵的故事。
公式推导
上述问题可以转化为求一元同余方程组的问题：
$
\begin{cases}
x=a_1\ mod\ m_1 \
x=a_2\ mod\ m_2 \
... \
x=a_n\ mod\ m_n
\end{cases}
$
求出x的值。
假设整数$m_1,m_2, ... ,m_n$两两互质，则对任意的整数：$a_1,a_2, ... a_n,$，该方程组有解，并且通解可以用如下方式得到：
令
$M=m_1 \times m_2 \times ... \times mn =\prod{i=1}^n m_i $
是整数$m_1,m_2, ... ,m_n$的乘积，并设$M_i=M/m_i$， 是除了$m_i$以外的n- 1个整数的乘,i在[1,n]之间。
设$t_i$为$M_i$模的逆元,则$t_iM_i \equiv 1 mod (m_i)$ , 方程组的通解形式为
$x=a_1t_1M_1+a_2t_2M_2+...+a_nt_nMn+kM=kM+ \sum{i=1}^n a_it_iM_i,k \in \mathbb{Z}$
K是整数，在模M的意义下，方程组只有一个解：
$x=(\sum_{i=1}^n a_it_iM_i)modM$
为什么这样求出来的解就是正确的呢？下面我们来证明。
解法证明
证明 ：
(1)从假设可知，对任何$i \in {1,2,...,n}$ ，因为$m_1,m_2...m_n$两两互质，
所以$m_i,M_i$互质。所以必然存在逆元$t_i,t_iM_i \equiv 1(mod\ m_i)$
可得下式成立，
$a_it_iM_i \equiv a_i mod (m_i)$
对于任意$\forall_j \in {1,2,...,n}(j\neq i)$
$a_it_iM_i \equiv 0 (mod\ m_j)$
所以：$\forall_i \in {1,2,...,n}$
$x=a_it_iMi+\sum{j\neq i}a_jt_jM_j \equiv ai+\sum{j\neq i}0(mod\ m_j)\equiv a_i(modm_i)$
这说明x就是方程组的解。
(2)如果$ x_1,x_2$都是方程组的解，那么:
$x_1-x_2 \equiv 0(mod\ m_i)$
而 $m_1,m_2,...,mn$两两互质,说明 $M =\prod{i=1}^n m_i $整除$x_1-x_2$, 所以方程组的任何两个解之间必然相差M的整数倍,
所以方程组所有的解的集合是:
$\lbrace Km+\sum_{i=1}^na_it_iM_i \rbrace $
实例演练
以上求解思路从下面两个结论出发：
-
两个数相加，如果一个加数能被a整除，另一个整数不能被a整除，那么它们的和就不能被整数a整除，和的余数取决于不能不能被a整除的加数
-
两数和不能整除a，若除数扩大（或缩小）n倍，而被除数不变，则其商和余数也同时扩大（或缩小）相同的倍数（余数必小于除数)
这两个结论显而易见，下面来实例解析下中国剩余定理求解过程。
通过开头提出的例子计算来帮助理解。
例中可得，$ a_1= 2, a_2= 3, a_3= 2, m_1= 3, m_2= 5, m_3= 7$
方程组为：
$
\begin{cases}
x=2\ mod\ 3 \
x=3\ mod\ 5 \
x=2\ mod\ 7
\end{cases}
$
<1> 计算最小公倍数 M = 3 57= 105
<2> 计算$M_1$=105/3 = 35, $M_2$= 105/5 = 21, $M_3$= 105/7 = 15
分别求出
$t_1$= 2, $t_2$=1, $t_3$=1 [注：求解逆元的方法参见]
解为：
$x = a_1t_1M_1+a_2t_2M_2 + a_3t_3M_3(mod\ M_i) = 140 + 63 + 30 (mod\ 105) = 23$
观察解 $x = a_1t_1M_1+a_2t_2M_2 + a_3t_3M_3(mod\ M_i )$ 结构，
其中$M_2,M_3$均能整除$m_1$, 后二者之和模 $m_1$为零，
根据结论1，x值取决于第一项$a_1t_1M_1$
由于$t_1M_1 \equiv 1mod(m_1)$ ,
根据结论2，将除数扩大$a_1$倍，余数也扩大$a_1$倍，即 $a_1t_1M_1 \equiv a_1mod(m_1)$(其实也是模运算的乘法规则，参见此历史文章)。
以上分析从模（$m_1$）的角度满足方程组第一个等式。同理， 从$m_2$角度类似分析，x满足方程组第二个等式，依次类推满足所有等式。
小结
本节主要介绍了中国剩余定理，也是数论中重要的定理之一。其中过程用到了模运算的乘法规则和逆元的求法，可见这一系列知识点是环环相扣的，层层递进的。
这两节文章又是为了更好理解RSA加解密原理章节而展开，前后联系，相互呼应以形成知识学习的闭环。
本来打算本节包含欧拉函数性质4的证明。但是篇幅不短了， 下次再说吧。
好了，有了中国剩余定理的基础，下一节讲欧拉函数性质4的推导。
欢迎关注公众号：blocksight
