How to use the linear diophantine equation solver
- Enter whole numbers for a, b and c in the equation a x + b y = c.
- Read the greatest common divisor. If it does not divide c, no whole-number solution exists.
- Otherwise read one solution and the general form, where t can be any whole number.
- When a and b are positive, check the count of solutions with x and y both at least 0 and the table that lists them.
Formula
g = gcd(a, b). Solutions exist exactly when g divides c.
Extended Euclid finds x1, y1 with a x1 + b y1 = g.
One solution: (x0, y0) = (x1 c / g, y1 c / g).
All solutions: x = x0 + (b / g) t, y = y0 - (a / g) t for whole t.
For a, b > 0, both unknowns are at least 0 for t from 0 to floor(y0 / (a / g)) once x0 is reduced into [0, b / g).
The page reduces x0 to the smallest value of at least 0, so the first row of the table is the solution with the smallest x.
Stamps and a tricky pair
For 3x + 5y = 22 the gcd is 1, so solutions exist. One is x = 4, y = 2, and all are x = 4 + 5t, y = 2 - 3t. Only t = 0 keeps both at least 0, so exactly one way works: four 3-unit pieces and two 5-unit pieces.
For 240x + 46y = 6 the gcd is 2, which divides 6. The Euclid steps give the solution x = 19, y = -99, and the general form x = 19 + 23t, y = -99 - 120t. No solution has both unknowns at least 0. For 4x + 6y = 7 the gcd 2 does not divide 7, so there are no solutions. Equation 13x + 17y = 1000 has 5 solutions with both unknowns at least 0.
When a solution exists
Every value of a x + b y is a multiple of gcd(a, b), because both terms are. So c must be a multiple of the gcd, and that condition is also enough: if it holds, the extended Euclidean algorithm builds a solution. This is the reason that you cannot make 7 from 4s and 6s, but can make any even total.
The same idea decides whether a linear congruence has a solution, which is covered in the modular arithmetic calculator. The greatest common divisor itself can be found with the GCF and LCM calculator.
Solutions in non-negative whole numbers
Many practical questions need x and y to be at least 0: how many of two package sizes make up an order, or which two coin values add to an amount. With positive a and b the solutions form a short stretch of the general family, and the page counts how many there are. A count of 0 means the total cannot be made in that way even though whole-number solutions exist.
The Euclid steps table shows the divisions used. For equations with squares and higher powers, other tools such as the quadratic equation solver apply.
Assumptions and limits
- All of a, b and c are whole numbers with absolute value up to 1,000,000,000,000.
- Solutions are whole numbers, which may be negative unless the count of non-negative solutions is shown.
- When a or b is 0 the equation reduces to one unknown, and the other unknown is free.
- The count of non-negative solutions is given only when a and b are both positive.
Frequently asked questions
What does t mean in the answer?
It is a free whole number. Each choice of t gives one pair (x, y) that solves the equation, and every solution comes from some t. Adding 1 to t moves x by b / g and y by minus a / g.
Why does the page show a negative y for some equations?
The general family often has negative members, and a particular solution can be negative for one unknown. The count of non-negative solutions tells you whether a solution with both at least 0 exists.
What if a and b share a factor with c?
Then you can divide the whole equation by the common factor first. The solver does this implicitly through the gcd, and the solutions are the same as for the reduced equation.
Is there a limit on the size of the numbers?
Inputs up to one trillion are accepted. The arithmetic uses exact whole numbers, so even large coefficients give exact answers without rounding.