What this calculator does
A Diophantine equation asks for whole-number solutions only, which is a much harder demand than allowing any real number. For ax + by = c the answer is decided entirely by one test: whether the greatest common divisor of a and b divides c.
When it does, there are infinitely many solutions rather than one. For 12x + 18y = 30 the gcd is 6, which divides 30, and the solutions run x = −5 + 3t, y = 5 − 2t for every whole number t.
The formula
The extended Euclidean algorithm finds one solution to ax + by = gcd(a, b). Scaling it by c over the gcd gives a particular solution, and the general form adds multiples of b over gcd and a over gcd.
| Term | Meaning |
|---|---|
| Diophantine equation | One where only integer solutions count. |
| Extended Euclidean algorithm | The method that finds both the gcd and the coefficients producing it. |
| General solution | The infinite family generated by adding multiples of b/g and subtracting multiples of a/g. |
The inputs explained
| Field | What to enter |
|---|---|
| a | Coefficient of x. |
| b | Coefficient of y. |
| c | The target value. Must be divisible by the gcd of a and b for any solution to exist. |
When to use it
Solving a coin or weight problem
Making an exact total from two denominations is exactly this equation.
Finding integer points on a line
The solutions are the lattice points the line passes through.
Cryptography groundwork
The extended Euclidean algorithm underpins modular inverses and RSA.
Worked examples
Every figure in the tables below is produced by this page’s own calculator at build time, so the numbers and the tool always agree. Select any row to load that scenario.
How does the target change the solution?
Three targets all divisible by the gcd.
| Target c | Particular solution (x₀, y₀) | General solution |
|---|---|---|
| c = 12 | -2, 2 | x = -2 + 3t, y = 2 − 2t |
| c = 30 | -5, 5 | x = -5 + 3t, y = 5 − 2t |
| c = 36 | -6, 6 | x = -6 + 3t, y = 6 − 2t |
Questions
Why must the gcd divide c?
Because every value of ax + by is a multiple of the gcd of a and b, whatever integers x and y take. If c is not such a multiple, no combination can reach it, which settles the question immediately.
Why are there infinitely many solutions?
Because adding b over the gcd to x while subtracting a over the gcd from y leaves the total unchanged. That adjustment can be applied any number of times in either direction.
How do I find only positive solutions?
By restricting the parameter t to the range where both x and y stay positive. That usually gives a finite set, and it is the form most real word problems actually want.
What is the connection to modular arithmetic?
A direct one. Solving ax ≡ c mod b is the same problem as ax + by = c, which is why the extended Euclidean algorithm is used for both modular inverses and Diophantine equations.
For finding a modular inverse, see the modular inverse calculator. For simultaneous congruences, see the Chinese remainder theorem calculator.