线性同余方程

定义

形如 (ax equiv c pmod b) 的方程称为线性同余方程
等价于 (ax + by = c) 因此有解条件为 ((a, b) mid c)

求解

任意的线性同余方程总可以判定为无解,或化为 (x equiv a pmod m) 的形式

方法

若 ((a, b) = 1) ,则 (x) 有唯一解 (x equiv a^{-1}c pmod b)
否则设 ((a, b) = d, a = a'd, b = b'd, c = c'd)
那么有 (a'x + b'y = c'), 即 (a'x equiv c' pmod {b'})
因为 ((a' , b') = 1)
所以 (x equiv (a')^{-1}c' pmod b')
所以任意的线性同余方程总可以判定为无解,或化为 (x equiv a pmod m) 的形式