Diophantine Equation Calculator
A linear Diophantine equation is an equation of the form ax plus by equals c where you are looking for integer solutions only, named after the ancient mathematician Diophantus. Such equations appear in number theory, cryptography and scheduling problems whenever quantities have to come in whole units. This calculator solves the two-variable case ax plus by equals c. The key fact is that integer solutions exist if and only if the greatest common divisor of a and b divides c, and when they do, there are infinitely many, forming a regular family. The calculator first finds the greatest common divisor of a and b using the extended Euclidean algorithm, which also returns the coefficients that express that divisor as a combination of a and b. Scaling those coefficients gives one particular solution, and the general solution is built from it by stepping x and y in opposite directions by b over the divisor and a over the divisor. You enter the three integers a, b and c, and the calculator reports whether solutions exist, one particular solution, and the general form. Every figure is computed deterministically by the extended Euclidean algorithm, never guessed. The method and a worked example that reconciles to the calculator default are shown in full below.
The equation a x + b y = c has integer solutions when gcd(a, b) divides c. For the default 4x + 6y = 10, gcd(4, 6) = 2 divides 10, and one particular solution is x = 1, y = 1.
Formula
a x + b y = c
Solvable in integers if and only if gcd(a, b) divides c
General: x = x0 + (b/g) t, y = y0 - (a/g) t, for any integer t
The extended Euclidean algorithm finds g = gcd(a, b) and integers u, v with a u + b v = g. If g divides c, scaling by c/g gives a particular solution, and all solutions follow by stepping x and y by b/g and a/g.
Worked example
Solve 4x + 6y = 10 for integers, with a = 4, b = 6 and c = 10.
- gcd(4, 6) = 2, and 2 divides 10, so solutions exist
- Extended Euclid gives 4(-1) + 6(1) = 2; scale by 10/2 = 5: 4(-5) + 6(5) = 10
- General: x = -5 + 3t, y = 5 - 2t; at t = 2, x = 1, y = 1
- Check: 4(1) + 6(1) = 10
These are the calculator's default inputs, so the particular solution x = 1, y = 1 reconciles with the widget.
Diophantine Equation Calculator: frequently asked questions
When does ax + by = c have integer solutions?
Exactly when the greatest common divisor of a and b divides c. If it does, there are infinitely many integer solutions; if it does not, there are none.
What is the extended Euclidean algorithm?
It is an extension of the usual algorithm for the greatest common divisor that also returns integers u and v satisfying a times u plus b times v equals the greatest common divisor. Those coefficients give a particular solution.
How many solutions are there?
When a solution exists there are infinitely many. From any particular solution you generate the rest by adding b divided by the gcd to x and subtracting a divided by the gcd from y, for each integer step.
Why might the particular solution differ from mine?
Any valid solution is correct; different methods land on different representatives of the same infinite family. The calculator shows one particular solution that satisfies the equation.
Are the results exact?
Yes. The extended Euclidean algorithm works in exact integer arithmetic, so the greatest common divisor and the particular solution are exact.
Official sources
- Number theory and integer algorithm reference: US National Institute of Standards and Technology (NIST). As at 25 June 2026.
Reviewed by the CalculatorHub team, edited by James Graham, 25 June 2026. See our methodology. This is general information, not financial, tax, legal or investment advice.