中国剩余定理

形式

解同余方程组

$\begin{cases} x \equiv b_1 \mod a_1\\ x \equiv b_2 \mod a_2 \\ x \equiv b_3 \mod a_3 \end{cases}$

示例

孙子问题
最早，在《孙子算经》中有这样一个问题：“今有物不知其数，三三数之剩二，五五数之剩三，七七数之剩二，问物几何？用白话描述就是，现在有一个数不知道是多少，只知道这个数除以3余2，除以5余3，除以7余2， 问这个数是多少？

转换为方程：

$\begin{cases} x \equiv 2 \mod 3\\ x \equiv 3 \mod 5 \\ x \equiv 2 \mod 7 \end{cases}$

要直接找到满足条件的x并不容易，但可以找$n_1,n_2,n_3$,使

$\begin{cases} n_1 \equiv 2 \mod 3\\ n_2 \equiv 3 \mod 5 \\ n_3 \equiv 2 \mod 7 \end{cases}$

令$x = n_1+n_2+n_3$

$x \equiv 2 \pmod 3 = (n_1+n_2+n_3) \equiv 2 \pmod 3$

$\because n_1 \equiv 2 \pmod 3$
要使上式成立，则$n_2,n_3要是3的倍数$
同理，

$(n_1+n_2+n_3) \equiv 3 \pmod 5\\ (n_1+n_2+n_3) \equiv 2 \pmod 7$

上式成立的条件分别是$n_1, n_3$是5的倍数。$n_1,n_2$是7的倍数
综上，
$n_1$既是5的倍数，又是7的倍数，所以$n_1$是35的倍数
$n_2$既是3的倍数，又是7的倍数，所以$n_2$是21的倍数
$n_1$既是3的倍数，又是5的倍数，所以$n_3$是15的倍数
同余方程组转换为：

$\begin{cases} 35m_1 \equiv 2 \pmod 3\\ 21m_2 \equiv 3 \pmod 5\\ 15m_3 \equiv 2 \pmod 7 \end{cases}$

由拓展欧几里得定理：

$\begin{cases} 35w_1 \equiv 1 \pmod 3\\ 21w_2 \equiv 1 \pmod 5\\ 15w_3 \equiv 1 \pmod 7 \end{cases}$

相当于求逆元

$\begin{cases} w_1 = inverse(35, 3)\\ w_2 = inverse(21, 5)\\ w_3 = inverse(15, 7) \end{cases}$

由比例关系

$\begin{cases} 35m_1 \equiv 2 \pmod 3\\ 35w_1 \equiv 1 \pmod 3 \end{cases}$

$\rightarrow m_1 = 2w_1$

同理：

$\begin{cases} m_1 = 2w_1\\ m_2 = 3w_2\\ m_3 = 2w_3 \end{cases}$

汇总：

$\begin{cases} n_1 = 35m_1 = 35 * 2w_1 = 35 * 2 * inverse(35, 3)\\ n_2 = 21m_2 = 21 * 3w_2 = 21 * 3 * inverse(21, 5)\\ n_3 = 15m_3 = 15 * 2w_3 = 15 * 2 * inverse(15, 7) \end{cases}$

求出$x=n_1+n_2+n_3$

姿势

将这个过程一般化

$设n=\prod_{i = 1}^{n}{a_i} \rightarrow 所有模数的乘积$

$r_i = \frac{n}{a_i} $ (35, 21, 15)
$w_i = inverse(r_i, a_i)$
$m_i = b_i * w_i$
$n_i = r_i * m_i$
所有$n_i$相加得$x$

eg:

t1 = inverse(q, p)
t2 = inverse(p, q)

m1 = (q*t1*c1 + p*t2*c2) % n
m2 = (q*t1*c1 + p*t2*cp2) % n
m3 = (q*t1*cp1 + p*t2*c2) % n
m4 = (q*t1*cp1 + p*t2*cp2) % n

珍贵手稿