中国剩余定理
最后更新于:2022年6月25日 下午
仅以此博文,感谢知乎好友 Vivr0
中国剩余定理也称孙子定理,是中国古代求解一次同余方程组的方法。
用现代的语言来说就是: \[ x \equiv \left\{ \begin{array}{cc} a_1 \mod m_1 \\ a_2 \mod m_2 \\ \vdots \\ a_n \mod m_n \end{array} \right. \] 且正整数组 \(m_i\) 两两互素,则对任意整数组 \(a_i\),上述方程有解,解可以写成 \(x \equiv a \mod m\)
我们不要求 \(m_i\) 两两互素也能求解,只是不一定有解,下面详细给出做法。
我们先考虑 \(n=2\) 的情形。即 \[ x \equiv \left\{ \begin{array}{cc} a_1 \mod m_1 \\ a_2 \mod m_2 \end{array} \right. \]
我们可以把方程写成
\[ \left\{ \begin{array}{lll} x - a_1 & \equiv \; 0 & \mod m_1 \\ x - a_1 & \equiv \; a_2-a_1 & \mod m_2 \end{array} \right. \]
我们设 \(d = \gcd(m_1,m_2)\),则 \(d| x-a_1\) 又 \(d|m_2\),所以 \(d|a_2-a_1\)。
我们知道对任意正整数 \(a,b\), 存在整数 \(x, y\) 使得 \(xa + yb = \gcd(a,b)\)。
(最后 Python 代码注释中有给出 \(x, y\) 的详细操作)
存在 \(t_1, t_2\) 使得 \(m_1 t_1 + m_2 t_2 = gcd(m_1, m_2) = d\),所以 \[ x-a_1 \equiv \frac{a_2-a_1}{d} (m_1t_1 + m_2t_2) \equiv \frac{a_2-a_1}{d} t_1 m_1 \mod m_2 \] 即 \(x \equiv a \mod m\),其中 \(a= a_1 + \frac{a_2-a_1}{d} t_1m_1 = \frac{t_2m_2a_1+t_1m_1a_2}{d}\),\(m = lcm(m_1,m_2) = \frac{m_1m_2}{d}\)
\(n-1\) 次上述操作,就处理了一般情况
C++ 代码
1 |
|
Python 代码
1 |
|