中国余数定理

Published: July 21, 2020 by Daltao

• Categories:
• algorithm 101

• 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$，这显然是不可能的。