Linear Diophantine Equation Calculator — Integer Solutions of ax + by = c

How it works

ax + by = c has integer solutions ⇔ g = gcd(a, b) divides c · extended Euclid: as + bt = g · particular solution x₀ = s·(c/g), y₀ = t·(c/g) · general: x = x₀ + (b/g)k, y = y₀ − (a/g)k, k ∈ ℤ

A linear Diophantine equation asks for whole-number solutions of ax + by = c. Every integer combination of a and b is a multiple of their gcd, so a solution exists exactly when gcd(a, b) divides c. The extended Euclidean algorithm writes the gcd as as + bt, and scaling by c/g gives one solution; all others differ by multiples of (b/g, −a/g). The calculator shifts the particular solution so x₀ is the smallest non-negative value and counts the solutions with both x and y positive (Rosen, Elementary Number Theory, §3.7).

Worked example

15x + 21y = 39: the Euclidean algorithm gives 21 = 1 × 15 + 6, 15 = 2 × 6 + 3, 6 = 2 × 3 + 0, so gcd = 3, which divides 39. Back-substituting, 15·3 + 21·(−2) = 3. Multiply by 13: x = 39, y = −26, then shift to the smallest non-negative x: (4, −1), since 15·4 + 21·(−1) = 39. General solution x = 4 + 7k, y = −1 − 5k. No solution has both x and y positive.

Sources: Wolfram MathWorld — Diophantine Equation (linear) · Wikipedia — Bézout’s identity

Frequently asked questions