线性同余方程

一个线性同余方程

(1)

有解 当且仅当 同余式

(2)

与 是 最大公约数 可解。设原方程的一个解为 。那么解为 , , , ..., 。如果 , 那么只有一个解 。

线性同余的解可以使用 Wolfram 语言 通过以下方式找到Reduce[a*x == b, x,Modulus ->m].

线性同余方程的解等价于找到分数 同余式 的值，对于分数同余式，存在一种贪婪型算法。特别地，(1) 可以被重写为

(3)

也可以写成

(4)

在这种形式下，解 可以通过以下方式找到Mod[b y, m]，其中 是 Wolfram 语言 函数返回的解PowerMod[a, , m]。这被称为 模逆。

两个或多个联立线性同余式

(5)

(6)

可以使用 中国剩余定理 求解。