初等數論/同餘方程

同餘方程簡介

形如 $a x \equiv b$ $(\mod y)$ 的方程求解通常采用换模法和缩小系数法

一次同餘方程組

$x \equiv a_{1} (\mod m_{1})$

$x \equiv a_{2} (\mod m_{2})$

......

$x \equiv a_{k} (\mod m_{k})$

若 $m_{1}, m_{2}, . . . . . ., m_{k}$ 這些數兩兩互質，且定義 $m_{i} M_{i} = m_{1} m_{2} . . . . . . m_{k}$ 以及 $C_{i} M_{i} \equiv 1 (\mod m_{i})$ 則此一次同餘方程組的解為：

$x \equiv a_{1} M_{1} C_{1} + a_{2} M_{2} C_{2} + . . . . . . + a_{k} M_{k} C_{k} (\mod m)$