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, Diophantine equations are very difficult to solve and there are many approaches. (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.
Edit Steps
- 1If it isn't already, put the equation in the form ax + by = c.
- 2Apply 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.
Euclid's algorithm shows that 87 and 64 are relatively prime. The quotients in red are needed later. - 3If 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.
- 4Build a three row table as shown.
Start like this. - 5Populate 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.
Add quotients to top row - 6Populate 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.
The table is now partially filled. - 7Look 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.
A completely filled table. The solution is hidden in the last two columns. - 8Notice 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.
- 9Return 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.
- 10Only 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.
- 11If 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.
Edit 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.
Edit Things You'll Need
Edit Related wikiHows
Articles for You to Write
Article Info
Featured Article
Last edited:
May 13, 2012 by Goldenzebra
Categories:
Featured Articles | Algebra
Recent edits by: Flickety, Maniac, Sailesh Patel (see all)
