Diophantine Equation Calculator

A linear Diophantine equation asks for whole-number solutions to ax + by = c, and whether any exist at all comes down to a single divisibility check: a solution exists exactly when the greatest common divisor of a and b divides c evenly, with no remainder. This calculator runs the Extended Euclidean Algorithm to compute that GCD and, in the same pass, two coefficients that express the GCD itself as a combination of a and b — a result called Bezout's identity. Those coefficients are then scaled by c divided by the GCD to produce one particular solution, x-naught and y-naught, that genuinely satisfies the original equation rather than an equation for the GCD alone.

Because a linear equation with integer solutions always has infinitely many of them, the calculator also reports the General Solution as a formula in a free parameter t: every integer value of t, positive, negative, or zero, produces another valid pair. At the default values of a = 3, b = 5, c = 1, the GCD of 3 and 5 is 1, which divides every integer including 1 itself, so a solution is guaranteed to exist before any arithmetic even starts. When a and b share a larger common factor that does not divide c, the calculator reports plainly that no integer solution exists — it does not fall back to showing the nearest approximate, non-integer answer, because none of the outputs here are meant to be read as anything but exact whole numbers.