中国剩余定理

阅读数:26 评论数: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下的逆元,再用逆元乘余数。