Linear Congruence Calculator — Solve ax ≡ b (mod m)

How it works

ax ≡ b (mod m) has a solution ⇔ g = gcd(a, m) divides b · divide through: (a/g)x ≡ (b/g) (mod m/g) · x₀ = (b/g)·(a/g)⁻¹ mod (m/g) · all solutions mod m: x₀ + k·(m/g), k = 0, 1, …, g − 1

A linear congruence is the modular version of ax = b. It is solvable exactly when g = gcd(a, m) divides b, and then it has exactly g solutions modulo m. Dividing a, b and m by g leaves a congruence whose coefficient is invertible, so one multiplication by the modular inverse (found with the extended Euclidean algorithm) gives the unique solution modulo m/g. Adding multiples of m/g lists every solution modulo m (Rosen, Elementary Number Theory, §4.2). Negative a or b are first reduced modulo m.

Worked example

14x ≡ 30 (mod 100): gcd(14, 100) = 2, and 2 divides 30, so there are 2 solutions. Divide by 2: 7x ≡ 15 (mod 50). The inverse of 7 mod 50 is 43 because 7 × 43 = 301 ≡ 1. Then x ≡ 15 × 43 = 645 ≡ 45 (mod 50). Modulo 100 the solutions are 45 and 95. Check: 14 × 45 = 630 ≡ 30 (mod 100).

Sources: Wolfram MathWorld — Linear Congruence Equation · Wikipedia — Linear congruence theorem

Frequently asked questions