How to Solve a Linear Diophantine Equation Philadelphia PA

Steps

1. If it isn't already, put the equation in the form ax + by = c.
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. 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. Build a three row table as shown.
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. 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. 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. 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. 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. Only now do we need to look at the constant term c on the right-hand side of the equation. Since the previous 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. 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.

Article provided by wikiHow, a wiki how-to manual. Please edit this article and find author credits at the original wikiHow article on How to Solve a Linear Diophantine Equation. All content on wikiHow can be shared under a Creative Commons license.