Linear Congruence Solver — Leandro Junes

Inputs

ax \equiv b \pmod n

Coefficient

a

Any integer.

Right-hand side

b

Any integer.

Modulus

n

Integer ≥ 1.

Try

Result

—

Solutions modulo $n$: —
$d=\gcd(a,n)$: —
$n'=n/d$: —

Solution steps

—

Method

Consider

ax \equiv b \pmod n

and let $d=\gcd(a,n)$ . A solution exists exactly when $d\mid b$ . If $d\nmid b$ , there is no solution.

If $d\mid b$ , divide the congruence by $d$ :

\frac{a}{d}\,x\equiv\frac{b}{d}\pmod{\frac{n}{d}}.

Now $\gcd\!\left(\tfrac{a}{d},\tfrac{n}{d}\right)=1$ , so $a/d$ has a modular inverse modulo $n/d$ . This gives one solution $x_0$ modulo $n/d$ . The complete set of incongruent solutions modulo $n$ is

x\equiv x_0+k\,\frac{n}{d}\pmod n,\qquad k=0,1,\dots,d-1.

Why $d$ solutions? The reduced congruence determines one residue class modulo $n/d$ . Inside a complete residue system modulo $n$ , that class occurs exactly $d$ times.

Two cases are handled directly. Modulo 1 every integer is congruent to every other, so every integer is a solution and there is a single residue class. If $a\equiv 0\pmod n$ the congruence reads $0\cdot x\equiv b\pmod n$ : every residue class is a solution when $b\equiv 0$ , and none otherwise.

Related: Modular Inverse — when $\gcd(a,n)=1$ the congruence has a unique solution, found directly with a modular inverse. Chinese Remainder Theorem — the natural next step, systems of congruences.