# wikiHow to Solve a Linear Diophantine Equation

A Diophantine equation is an algebraic equation with the additional restriction that we are only concerned with solutions in which the variables are integers. In general, there are many approaches for solving Diophantine equations. (Fermat's Last Theorem is a famous Diophantine equation that sat unsolved for over 350 years.)

However, linear Diophantine equations of the form ax + by = c can be solved relatively easily by the algorithm described here. By using this method, we can find (4,7) as the only solution in positive integers to 31x + 8y = 180. Division in modular arithmetic can also be expressed as a linear Diophantine equation. For example, 12/7 (mod 18) asks for the solution to 7x = 12 (mod 18) and can be rewritten as 7x = 12 + 18y or 7x - 18y = 12. While some of the diophantine equations are extremely difficult to solve, you can give this one a try.

## Steps

1. 1
If it isn't already, put the equation in the form ax + by = c.

2. 2
Apply Euclid's Algorithm to the coefficients a and b. This has two purposes. First, we want to know if a and b have a common factor. If we are trying to solve 4x + 10y = 3, we can then quickly assert that since the left-hand side is always even and the right-hand side always odd, no integer solutions exist. Similarly, if we had 4x + 10y = 2, we could simplify the problem to 2x + 5y = 1. The second reason is that, provided a solution exists, we can construct one from the sequence of quotients obtained from Euclid's Algorithm. 3. 3
If a, b, and c have a common factor, then simplify the equation by dividing the left and right sides of the equation by that factor. If a and b have a common factor not shared by c, then stop. There are no integer solutions.

4. 4
Build a three row table as shown. 5. 5
Populate the top row of the table with the quotients from Euclid's Algorithm. The image shows how this would look for solving 87x - 64y = 3.
6. 6
Populate the bottom two rows from left to right by the following procedure: For each cell, compute the product of the top cell of that column and the cell immediately to the left of the empty cell. Fill the empty cell with that product plus the value two cells to the left.
7. 7
Look at the last two columns in the completed table. The final column should contain a and b, the coefficients from the equation in step 3. (If not, recheck your calculations.) The second to last column will contain two other numbers. In the example with a = 87 and b = 64, the penultimate column contains 34 and 25.
8. 8
Notice that 87*25 - 64*34 = -1. The determinant of the 2x2 matrix in the lower right will always be either plus or minus 1. If negative, multiply both sides of the identity by -1 to get -87*25 + 64*34 = 1. This observation is the starting point from which we can build a solution.

9. 9
Return to the original equation. Rewrite the identity in the previous step as either 87*(-25) + 64*(34) = 1 or 87*(-25) - 64*(-34) = 1, whichever best resembles the original equation. For the example, the second choice is preferred since it matches the -64y term in the original when y = -34.

10. 10
Only now do we need to look at the constant term c on the right-hand side of the equation. Since the previous equation demonstrates a solution to ax + by = 1, multiplying both sides by c to get a(cx) + b(cy) = c. If (-25, -34) is a solution to 87x - 64y = 1, then (-75, -102) is a solution to 87x-64y = 3.

11. 11
If a linear Diophantine equation has any solutions, then it has infinitely many solutions. This is because ax + by = a(x+b) + b(y-a) = a(x+2b) + b(y-2a), and in general ax + by = a(x+kb) + b(y-ka) for any integer k. Therefore, since (-75,-102) is a solution to 87x-64y = 3, other solutions are (-11,-15), (53,72), (117,159), etc. The general solution could be written as (53+64k, 72+87k) where k is any integer.

## Tips

• You should be able to do this with pencil and paper, but when working with larger numbers, a calculator, or better yet, a spreadsheet can be very helpful.
• Check your answer. The identity in step 8 should catch any errors made in Euclid's algorithm or in filling out the table. Checking the final answer against the original equation should catch any other errors.

## Things You'll Need

• Pencil and paper, maybe a calculator

## Article Info

Featured Article

Categories: Featured Articles | Algebra