numvana

Linear Diophantine Equation Solver

Solve ax + by = c for integer solutions x and y using the extended Euclidean algorithm, including the full family of solutions, not just one.

Solvable?
Yes
GCD(a, b)
1
One solution (x, y)
(22, -11)
All solutions
x = 22 + 5t, y = -11 + -3t, for any integer t

How it works

A linear Diophantine equation ax + by = c asks for integer solutions only — no fractions allowed — which is a genuinely different question from solving it over real numbers (where a solution always exists for any line that isn't degenerate). This calculator uses the extended Euclidean algorithm, the same algorithm this site's Chinese Remainder Theorem and Modular Inverse calculators rely on, which finds gcd(a, b) together with one particular pair (x₀, y₀) satisfying a·x₀ + b·y₀ = gcd(a, b) — Bézout's identity.

An integer solution to the original equation exists exactly when gcd(a, b) divides c evenly. When it does, scaling that particular pair by c ÷ gcd(a, b) gives one valid solution immediately. When it doesn't — for example 2x + 4y = 7, since gcd(2, 4) = 2 never divides evenly into an odd number — no integer x and y can ever satisfy the equation, no matter how large.

A linear Diophantine equation that has one solution actually has infinitely many: starting from any particular solution, stepping x by b ÷ gcd(a, b) and y by −a ÷ gcd(a, b) at the same time always lands on another valid solution, since those two steps' contributions to a·x + b·y exactly cancel. This calculator reports that general family, not just a single answer.

FAQ

Why does 2x + 4y = 7 have no integer solution, even though 2x + 4y = 8 does?

The left side, 2x + 4y, is always even for any integers x and y, since it's 2 times (x + 2y). 7 is odd, so it can never equal 2x + 4y no matter what integers you try — but 8 is even, so plenty of integer pairs work (x = 4, y = 0, for instance). This is exactly the gcd divisibility rule: gcd(2, 4) = 2 divides 8 but not 7.

Is the 'one solution' this calculator shows the only correct answer?

No — it's just the particular solution the extended Euclidean algorithm happens to land on first; any other pair generated by the general-solution formula (stepping by b/gcd and −a/gcd) is equally valid and satisfies the same equation. The 'All solutions' line is the actual complete answer; the single pair is only a starting point for it.

Related calculators