[数论]中国剩余定理
SkyLiYu
·
·
个人记录
简介
中国剩余定理 (Chinese Remainder Theorem, CRT) 可求解如下形式的一元线性同余方程组（其中m_1,m_2,...,m_k 互质）
\left\{\begin{array}{ccc}
{x} & {\equiv} & {a_{1}\left(\bmod \ m_{1}\right)} \\
{x} & {\equiv} & {a_{2}\left(\bmod \ m_{2}\right)} \\
{} & {\vdots} & {} \\
{x} & {\equiv} & {a_{n}\left(\bmod \ m_{k}\right)}
\end{array}\right.
算法
-
设M=\prod_{i=1}^{k} m_{i} \ , \ M_{i}=\frac{M}{m_{i}} \ , \ M_{i} t_{i} \equiv 1 \ \left(\bmod m_{i}\right) , 其中 1 \leq i \leq k ,
-
构造出一通解 x=\sum_{i=1}^{k} a_{i} M_{i} t_{i} ,
-
得 任意解为 x_0 = x+k * M ,
-
得 最小整数解 为 x_{min} = x_0 \% M .
证明
当 i \neq j 时 ， 有
a_{j} M_{j} t_{j} \equiv 0\left(\bmod \ m_{i}\right)
当 i = j 时 ， 有
a_{i} M_{i} t_{i} \equiv a_{i}\left(\bmod \ m_{i}\right)
故满足\sum_{i=1}^{k} a_{i} M_{i} t_{i} \equiv a_{i}\left(\bmod \ m_{i}\right)