Linear congruence solver

How it works

The congruence $a x \equiv b \pmod n$ asks for the $x$ for which $a x - b$ is a multiple of $n$. Let $g = \gcd(a, n)$. Every number of the form $a x - k n$ is a multiple of $g$, so there is a solution only if $g$ divides $b$.

If it does, divide everything by $g$: $(a/g)\, x \equiv b/g \pmod{n/g}$. Now $a/g$ and $n/g$ are coprime, so $a/g$ has an inverse modulo $n/g$ (extended Euclidean algorithm), and multiplying by it gives the unique solution $x_0$ modulo $n/g$. Modulo the original $n$ this is $g$ solutions: $x_0, x_0 + n/g, \dots, x_0 + (g-1)\, n/g$.

Example: $14 x \equiv 30 \pmod{100}$. Here $g = 2$ divides $30$, the reduced congruence is $7 x \equiv 15 \pmod{50}$, $7^{-1} \equiv 43$, so $x \equiv 45 \pmod{50}$: the solutions modulo 100 are $45$ and $95$. The same method solves the equation $a x + n y = b$ in integers.