中国剩余定理（CRT）学习笔记
PCSJZ
·
·
算法·理论
中国剩余定理（CRT）
CRT 可以用来解决像这样的线性同余方程组。
& x \equiv a_1 \pmod {m_1} \\
& x \equiv a_2 \pmod {m_2}\\
& ... \\
& x \equiv a_k \pmod {m_k} \\
\end{cases}
乘法逆元和扩展欧几里得
乘法逆元和扩展欧几里得（exgcd）可以认为是学习 CRT 的必要条件。
乘法逆元
若有 ax \equiv 1 \pmod b，则称 x 为 a \bmod b 意义下的乘法逆元。或者可以称 a 为 x 的乘法逆元。记作 a^{-1} 或者 [a^{-1}]_b。
扩展欧几里得（exgcd）
exgcd 可以用来求类似于 ax + by = \gcd(a, b)。
推导过程如下：
当 b=0 时，ax + by = a，故而 x = 1, y = 0。
当 b \ne 0 时，先使用欧几里得算法，得：
我们可以理解成“一一对应”，即 $a$ 对应 $b$，$b$ 对应 $a \% b$。
于是有：
左边 $=bx + (a \bmod b)y$。
$\because a \bmod b = a - \left \lfloor \frac{a}{b} \right \rfloor b
\therefore$ 左边 $=bx + (a - \left \lfloor \frac{a}{b} \right \rfloor b) \, y
\therefore$ 左边 $=ay+b(x- \left \lfloor \frac{a}{b} \right \rfloor y)
设有一组解使原方程组成立，即
& x =x_0 \\
& y=y_0 \\
\end{cases}
然后通过以一一对应，得到：
& x = y_0 \\
& y = x_0 - \left \lfloor \frac{a}{b} \right \rfloor y_0 \\
\end{cases}
费马小定理求乘法逆元
当 \gcd(a,p)=1 时，有 a^{p-1} \equiv 1 \pmod m。
那么可以看做 a^{p-2} \times a \equiv 1 \pmod m。
所以 a 的乘法逆元就是 a^{p-2}。
CRT 的求解通解
注：这种情况只支持对于每个 m_i 两两互质，其他情况需使用扩展中国剩余定理。
举个例子
求解关于 x 的线性同余方程组
x \equiv 2 \pmod 3 \\
x \equiv 3 \pmod 5 \\
x \equiv 2 \pmod 7 \\
\end{cases}
我们先构造使得 x = 2r_1+3r_2+2r_3，其中
$\begin{cases}
r_1 \equiv 1 \pmod 3 \\
r_1 \equiv 0 \pmod 5 \\
r_1 \equiv 0 \pmod 7 \\
\end{cases}
$\begin{cases}
r_2 \equiv 0 \pmod 3 \\
r_2 \equiv 1 \pmod 5 \\
r_2 \equiv 0 \pmod 7 \\
\end{cases}
$\begin{cases}
r_3 \equiv 0 \pmod 3 \\
r_3 \equiv 0 \pmod 5 \\
r_3 \equiv 1 \pmod 7 \\
\end{cases}
$\therefore r_1 = 35k_1, k_1 \in \mathbb{Z}
\because r_1 \equiv 1 \pmod 3
\therefore 35k_1 \equiv 1 \pmod 3
\therefore k_1=[35^{-1}]_3=2 + 3t_1(t_1 \in \mathbb{Z})
同理可以解得：
r_1 = 35 \times (2+3t_1) = 70 + 105t_1 \, \, (t_1 \in \mathbb{Z}) \\
r_2 = 21 \times (1 + 5t_2) = 21 + 105t_2 \, \, (t_2 \in \mathbb{Z}) \\
r_3 = 15 \times (1 + 7t_3) = 15 + 105t_3 \, \, (t3 \in \mathbb{Z}) \\
\end{cases}
代会 x = 2r_1+3r_2+2r_3，得
x = 140 + 63 + 30 + 6t_1 + 15t_2 + 14t_3 = 233 + 105(t_1+t_2+t_3)
$\therefore x = 233 + 105t
### 通解
令 $M = \prod_{i=1}^{k} m_i，M_i=\frac{M}{m_i}$。
设 $x=\sum_{i=1}^{k}a_ir_i$，$r_i=M_it$。
$t$ 为 $M_i$ 的乘法逆元。
### 至此，结束