中国余数定理

Published: by Creative Commons Licence

  • Tags:

中国余数定理

假设存在$k$个互质的整数,$m_1,m_2,\ldots,m_k$,记$m=m_1m_2\cdots m_k$。

对于任意整数$x<m$,记:

$x_i=x \mod m_i$

我们定义函数$f$,使得$f(x)=(x_1,x_2,\ldots,x_k)$。

命题1:$f$是定义域为$[0,m)$,值域为$[0,m_1)\times [0,m_2)\times \ldots \times x[0,m_k)$的双射函数

证明:

记$n_i=\frac{m}{m_i}$

由于$n_i$与$m_i$互质,因此,存在$r_i$使得$r_in_i=1(mod\phantom{1} m_i)$。(利用扩展欧几里得公式可以得到)

记$c_i=r_in_i$

很显然对于任意$j\neq i$,$c_i=0 (mod\phantom{1} m_j)$

而对于$j=i$,有$c_i=1(mod\phantom{1} m_i)$

因此$c_i=(0,…,0,1,0,…,0)$,其中仅第$i$位为$1$,其它位均为$0$。

我们实际上找打了一组基$c_1,…,c_k$。

而$a_1c_1+\cdots +a_kc_k=(a_1,a_2,…,a_k)$

因此我们可以从任一值域中的值还原出定义域上的值,因此$f$是满射。

由于定义域和值域的大小均为$m$,因此$f$一定是双射。

命题2:若f(x)=(a,a,…,a),那么我们必定有x=a(mod m)

证明:

首先f(a)=(a,…,a),且f是双射,因此结果显然。

扩展中国余数原理

中国余数定理需要$m_1,m_2,\ldots,m_k$互质,而在非互质的情况下,同样可以使用扩展中国余数定理来进行求解。

考虑前两个条件,可知:

记$g=gcd(m_1,m_2)$,很显然上式有解当且仅当$g|(x_2-x_1)$。若满足,则可以利用扩展欧几里得算法获得线性方程:$am_1+bm_2=g$,之后,令$k_1=\frac{a(x_2-x_1)}{g}$,从而得到$x_{12}=k_1m_1+x_1$。

当然上面提到的算法只能使用于k=2的情形。我们注意到前两条公式等价于$x=x_{12}(mod \phantom{1} m_{12}) (1,2)$,其中$m_{12}=lcm(m_1,m_2)$。用集合的角度来看待问题,记集合$X$表示满足所有$k$个条件的$x$的集合,而$X'$表示满足将$k$个条件中$(1),(2)$替换为$(1,2)$的$x$的集合。很显然对于任意满足性质$(1,2)$的$x$也应该同样满足也应该同样满足$(1)$和$(2)$,即$X' \subseteq X$。而假如存在两个不同的$x$,$y$,同时满足条件$(1)$和$(2)$,可得:

因此可知$y=x(mod\phantom{1}m_{12})$,即能同时满足$(1)$和$(2)$的$x$在模$m_{12}$的情况下是唯一的。由于$X$中的任意元素必定同时满足$(1)$和$(2)$的,因此该元素也属于$X'$,即$X' \supseteq X$,因此$X'=X$。

我们可以将条件$(1)$和$(2)$替换为条件$(1,2)$,这样我们只需要找出满足$k-1$个条件的$x$,重复这个过程,直到只剩下一个条件,这时候结果就显然易见了。

实际上扩展中国余数定理和中国余数定理的时间复杂度是相同的,但是扩展中国余数定理好像要更加实用。