Linear Diophantine Equation Solver
Finds all integer solutions to a linear Diophantine equation of the form ax + by = c. Use it when you need exact integer answers in problems involving divisibility, coin combinations, or scheduling.
About this calculator
A linear Diophantine equation has the form ax + by = c, where a, b, and c are integers and you seek integer solutions (x, y). Solutions exist if and only if gcd(a, b) divides c — otherwise the equation has no integer solutions. The extended Euclidean algorithm finds a particular solution (x₀, y₀) satisfying ax₀ + by₀ = gcd(a,b). Scaling by c/gcd gives a particular solution to the original equation. The complete general solution is then x = x₀ + (b/gcd)·t and y = y₀ − (a/gcd)·t for every integer t. This parametric family captures every integer solution to the equation.
How to use
Suppose you want to solve 6x + 10y = 14. Enter a = 6, b = 10, c = 14, and choose 'general' solution type. First, gcd(6, 10) = 2, which divides 14, so solutions exist. The extended Euclidean algorithm gives 6·(2) + 10·(−1) = 2, scaling by 14/2 = 7 yields x₀ = 14, y₀ = −7. The general solution is x = 14 + (10/2)t = 14 + 5t and y = −7 − (6/2)t = −7 − 3t for any integer t. For t = −2, for example: x = 4, y = −1.
Frequently asked questions
What does it mean when the calculator says 'no integer solutions' for ax + by = c?
It means that gcd(a, b) does not divide c. By Bezout's identity, every integer linear combination of a and b is a multiple of gcd(a, b). If c is not such a multiple, no pair of integers (x, y) can satisfy the equation. For example, 4x + 6y = 5 has no solution because gcd(4, 6) = 2 does not divide 5. You would need to adjust c to be an even number for solutions to exist.
How do I find all integer solutions to a linear Diophantine equation from one particular solution?
Once you have a particular solution (x₀, y₀), the full solution set is x = x₀ + (b/d)·t and y = y₀ − (a/d)·t, where d = gcd(a, b) and t ranges over all integers. Every integer value of t produces a valid solution, giving infinitely many solutions when they exist. The calculator returns this parametric form when you select the 'general' solution type. Substituting different values of t lets you find solutions within a specific range.
When would I use a linear Diophantine equation solver in real life?
Classic applications include the 'coin problem' — for instance, finding how many 3-cent and 5-cent stamps combine to make exactly 41 cents. It also appears in modular inverse calculations, scheduling problems where events repeat on different cycles, and Chicken McNugget-style combinatorics. Whenever you need whole-number quantities that satisfy a linear constraint, a Diophantine solver gives you all possibilities systematically rather than by trial and error.