中国余数定理

Published: by Creative Commons Licence

  • Tags:

UPD:之前写的内容自己都看不懂了,现在重写一下。中国余数定理应用范围不如扩展中国余数定理,并且并没有性能上的优势,因此不写了,这里只讲扩展中国余数定理。

扩展中国余数定理

扩展中国余数定理允许我们寻找一个数$x$,满足$x=y_i\pmod {m_i}$,其中$1\leq i\leq n$。

当$n=1$的时候,很显然$x=y_1$,且在模$lcm(m_1)$意义下唯一。

考虑$n>1$的情况。我们先考虑前两个等式$x=y_1\pmod {m_1}$和$x=y_2\pmod {m_2}$。

这时候等价我们要找两个非负整数$k_1$和$k_2$,满足$x=y_1+k_1 m_1$以及$x=y_2+k_2 m_2$。合并两个公式可以得到$y_1+k_1m_1=y_2+k_2m_2$。稍微转移一下项可以得到$k_1m_1-k_2m_2=y_2-y_1$。这个公式应该看起来很眼熟,这不是扩展欧几里德算法吗。记$g=gcd(m_1,m_2)$,这个公式有解当且仅当$g\mid y_2-y_1$。

可以发现剩下的问题规模变小了,用相同的技术解决即可。

并且在有解的情况下,可以发现$x$在模$lcm(m_1,\ldots,m_n)$的意义下是唯一的。实际上考虑$n=2$的情况,记$L=lcm(m_1,m_2)$,有$x=y_1+k_1 m_1$以及$x=y_2+k_2 m_2$。假设存在两个不同解$x_1,x_2$,且$0\leq x_1,x_2<L$。那么考虑到$m_1\mid x_1-x_2$以及$m_2\mid x_1-x_2$,因此一定有$L\mid x_1-x_2$,这显然是不可能的。