上一节介绍了欧拉定理和欧拉函数并加以证明。其中欧拉函数是积性函数的证明用到了中国剩余定理【欧拉函数性质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
如果觉得我的文章对您有用,请随意打赏。你的支持将鼓励我继续创作!