中國剩餘定理斷言,對于同餘方程組 \(x \equiv a_i \pmod{m_i} \ (i = 1...n)\)
若 \(m_i\) 兩兩互質,則 \(x\) 在 \(\pmod{M}\) 下有唯一解。這裡 \(M = m_1 m_2 ...m_n\)
中國剩餘定理同時也給出了構造解的方法:
令 \(M = m_1 m_2 ...m_n ,M_i = \frac {M}{m_i}\)
顯然 \((M_i ,m_i ) = 1\),是以 \(M_i\) 關于模 \(m_i\) 的逆元存在。把這個逆元設為 \(t_i\)
于是有:$M_i t_i \equiv 1 \ \pmod{m_i} $ , \(M_i t_i \equiv 0 \ \pmod{m_j} \ (j \not= i)\)
進一步:\(a_i M_i t_i \equiv a_i \ \pmod{m_i} ,a_i M_i t_i \equiv 0 \ \pmod{m_j} \ (j \not= i)\)
是以解為 \(x \equiv a_1 M_1 t_1 + a_2 M_2 t_2 + ... + a_n M_n t_n \ \pmod{M}\)
code
int inv(int a, int b) {
int x, y;
exgcd(a, b, x, y);
return x;
}
int CRT(const int a[], const int m[], n) {
int M = 1, ret = 0;
for (int i = 1; i <= n; i++) M *= m[i];
for (int i = 1; i <= n; i++) {
int Mi = M / m[i], ti = inv(Mi, m[i]);
ret = (ret + a[i] * Mi * ti) % mod;
}
return ret;
}
原生例題
今有物不知其數, 三三數之剩二, 五五數之剩三, 七七數之剩二, 問物幾何?
\(x \equiv 2 \ \pmod 3 ...... (1)\)
\(x \equiv 3 \ \pmod 5 ...... (2)\)
\(x \equiv 2 \ \pmod 7 ...... (3)\)
解
\(a_i = {2,3,2},m_i = {3,5,7},M = 3 ∗ 5 ∗ 7 = 105\)
\(M_i = \{\frac{105}{3},\frac{105}{5},\frac{105}{7} \} = \{35,21,15 \}\)
\(m_i = \{ inv(35,3),inv(21,5),inv(15,7) \} = \{2,1,1 \}\)
\(x \equiv 2 \times (35 \times 2) + 3 \times (21 \times 1) + 2 \times (15 \times 1)\)
\(x \equiv 233 \equiv 23 \ \pmod{105}\)