数学(4)——中国剩余定理
Reywmp
·
·
个人记录
有如下一元线性同余方程组（保证n_1, n_2, \cdots, n_k互质）。
\begin{cases}
x &\equiv a_1 \pmod {n_1} \\
x &\equiv a_2 \pmod {n_2} \\
&\vdots \\
x &\equiv a_k \pmod {n_k} \\
\end{cases}
\texttt{Solving}
求出
\N=\prod_{i=1}^{k}n_i
分别计算
m_i=\frac{\N}{n_i},m_i^{-1} \ (m_i \bmod n_i)
得到每个
c_i=m_i\times m_i^{-1}
可以得出方程组的唯一解是
x=\sum_{i=1}^{k}a_i\times c_i (\bmod \N)
\texttt{Proof}
取第 i 个和第 j 个( i\neq j )，有 m_j \equiv 0 \pmod {n_i}
\therefore c_j\equiv m_j \equiv 0 \pmod{n_i}
又 \ c_i\equiv m_i (m_i^{-1} \bmod n_i)\equiv 1 \pmod{n_i}
\begin{aligned}
\therefore x&\equiv \sum_{j=1}^{k} a_j \times c_j & \pmod{n_i}\\
&\equiv a_i \times c_i & \pmod{n_i}\\
&\equiv a_i \times m_i & \pmod{n_i}\\
&\equiv a_i &\pmod{n_i}
\end{aligned}
对于任意的 i\in [1,k] , 满足 x \equiv a_i \pmod{n_i}
\texttt {QED}
求逆元多种方法都可以，这里 n_i 不一样所以线性推貌似不能用，建议用 exgcd()
未完待续……
如果遇到不保证 n_i 互质的情况怎么办。
不互质会导致 m_i^{-1}\pmod{n_i} 不存在，因为存在任意一组 n_i,n_j 不互质就会导致存在 m_i 与 n_i 不互质，因为 m_i 中自然有 n_j 这个因子。显然 m_i^{-1} 也不存在。
那么如何解决这个问题呢，因为不互质是成队出现的情况，所以我们只需要将那些不互质组的分离再求解，然后再合并这些解就可以解决了，具体实现方法就是关键字合并。
稍微进行一下推导，写式子我还是不太在行。
假设子任务方程组是前两个。
\begin{cases}
x \equiv a_1 \pmod{n_1} \\
x \equiv a_2 \pmod{n_2}
\end{cases}
那么可以表示为
\begin{cases}
x = a_1 + k_1n_1 \\
x = a_2 + k_2n_2
\end{cases}
k_1n_1-k_2n_2=a_2-a_1\\
约定 G= \gcd(n_1,n_2)\\
\frac{n_1}{G}k_1-\frac{n_2}{G}k_2=\frac{(a_2-a_1)}{G}\\
\therefore \frac{n_1}{G}k_1\equiv \frac{(a_2-a_1)}{G}\pmod{\frac{n_2}{G}}\\
k_1\equiv(\frac{n_1}{G})^{-1}\times\frac{(a_2-a_1)}{G}\pmod{\frac{n_2}{G}}\\
\therefore k_1=(\frac{n_1}{G})^{-1}\times\frac{(a_2-a_1)}{G}+\frac{n_2}{G}\times y
带入 x=a_1+k_1n_1
x=a_1+((\frac{n_1}{G})^{-1}\times\frac{(a_2-a_1)}{G}+\frac{n_2}{G}\times y)\times n_1\\
x=a_1+(\frac{n_1}{G})^{-1}\times\frac{(a_2-a_1)}{G}\times n_1+\frac{n_2n_1}{G}\times y \\
x\equiv (\frac{n_1}{G})^{-1}\times\frac{(a_2-a_1)}{G}\times n_1+a_1 \pmod{\frac{n_1n_2}{G}}
我们发现 \displaystyle \frac{n_1n_2}{G} 就是 \text{lcm} (n_1,n_2)
所以就可以一直通过以上式子合并，如果合并时发现无解就自然整个方程组无解。
Reference: