阅读数:101 评论数:0

用现代数的语言来说明的话，中国剩余定理给出了以下的一元线性同余方程组

$\left\{ \begin{aligned} x&\equiv a_1 (mod\quad m_1) \\x&\equiv a_2 (mod\quad m_2)\\ &.\\&.\\&.\\x&\equiv a_n(mod\quad m_n) \end{aligned} \right.$

中国剩余定量说明：假设整数$m_1,m_2,\cdots,m_n$其中任两个数互质，则对任意的整数$a_1,a_2,\cdots,a_n$，方程组有解，并且通解可以用如下方式构造得到

（1）设$M=m_1\times m_2\times\cdots\times m_n=\prod\limits_{i=1}^{n}m_i$是整数$m_1,m_2,\cdots,m_n$的乘积，并设$M_i=\dfrac{M}{m_i},\quad \forall\in{1,2,\cdots,n}$，即$M_i$是除$m_i$以外的n-1个整数的乘积。

（2）设$t_i=M_i^{-1}$为$M_i$模$m_i$的逆元：$t_iM_i\equiv 1\quad (mod\quad m_i)$

（3）方程组的通解形式为$x=a_1t_1M_1+a_2t_2M_2+\cdots+a_nt_nM_n+kM=kM+\sum\limits_{i=1}^{n}a_it_iM_i,\quad k\in Z$。

下面用一个具体的例子，说明一下实际中是怎么使用的：

设总数为n，模a得x，模b得y，模c得z，若已知x，y，z，让求出最小的n。

则n=(x*a1+y*b1+z*c1)%d;

其中

a1=y*z中的倍数中模a等于1的最小的数；

b1=x*z中的倍数中模b等于1的最小的数；

c1=x*y中的倍数中模c等于1的最小的数；

d=a,b,c的最小公倍数。

中国剩余定理原版之韩信点兵版:

传说韩信点兵时发明的算法。设士兵总数为n，模3得x，模5得y，模7得z，若已知x，y，z，让求出最小的n。

则n=(x*70+y*21+z*15)%105;

可以用下面的小诗帮助记忆。

三人成行七十稀；70为35（5×7）的倍数中模3等于1的最小的数；

五树梅花廿一枝；21为21（3×7）的倍数中模5等于1的最小的数；

七子团圆月正半；15为15（3×5）的倍数中模7等于1的最小的数；

除百零五便得之。105为3，5，7的最小公倍数。

如果不是3，5，7用同样的方法求解。

补充一下

    以一个例子：“一个数除愉3余2，除以5余3，除以7除2”，我们试着揣测一下是如何推导出这个解法的：

    首先，我们假设n1是满足除以3余2的一个数，n2是满足除以5余3的数，n3是除以7除2的数。

    为了使n1+n2+n3即为我们要求的数，可推出：

（1）为使n1+n2+n3的和满足除以3余2，n2和n3必须是3的倍数

（2）为使n1+n2+n3的和满足除以5余3，n1和n3必须是5的倍数

（3）为使n1+n3+n3的和满足除以7余2，n1和n2必须是7的倍数

整理一下：

（1）n1除以3余2，且是5和7的倍数

（2）n2除以5余3，且是3和7的倍数

（3）n3除以7余2，且是3和5的倍数

在求n1,n2,n3时又用了一个小技巧，以n1为例，并非从5和7的公倍数中直接找一个除以3余2的数，而是先找一个除以3余1的数，再乘以2。也就是先出5和7和公倍数模3下的逆元，再用逆元乘余数。