A Diophantine (or Diophantine) equation is an algebraic equation whose solutions are sought for which the variables assume integer values. In general, the Diophantine equations are rather difficult to solve and there are several approaches (Fermat's last theorem is a famous Diophantine equation that has remained unsolved for over 350 years).
However, the linear diophantine equations of the type ax + by = c can be easily solved using the algorithm described below. Using this method, we find (4, 7) as the only positive integer solutions of the equation 31 x + 8 y = 180. The divisions in modular arithmetic can also be expressed as diophantine linear equations. For example, 12/7 (mod 18) requires the solution 7 x = 12 (mod 18) and can be rewritten as 7 x = 12 + 18 y or 7 x - 18 y = 12. Although many Diophantine equations are difficult to solve, you can still give it a try.
Steps
Step 1. If it is not already, write the equation in the form a x + b y = c
Step 2. Apply Euclid's algorithm to coefficients a and b
This is for two reasons. First, we want to find out if a and b have a common divisor. If we are trying to solve 4 x + 10 y = 3, we can immediately state that, since the left side is always even and the right side always odd, there are no integer solutions for the equation. Similarly, if we have 4 x + 10 y = 2, we can simplify to 2 x + 5 y = 1. The second reason is that, having proved that there is a solution, we can construct one from the sequence of quotients obtained through the Euclid's algorithm.
Step 3. If a, b and c have a common divisor, simplify the equation by dividing the right and left sides by the divisor
If a and b have a common divisor between them but this is not also a divisor of c, then stop. There are no whole solutions.
Step 4. Build a three-line table as you see in the photo above
Step 5. Write the quotients obtained with Euclid's algorithm in the first row of the table
The image above shows what you would get by solving the equation 87 x - 64 y = 3.
Step 6. Fill in the last two lines from left to right by following this procedure:
for each cell, it calculates the product of the first cell at the top of that column and the cell immediately to the left of the empty cell. Write this product plus the value of two cells to the left in the empty cell.
Step 7. Look at the last two columns of the completed table
The last column should contain a and b, the coefficients of the equation from step 3 (if not, double check your calculations). The penultimate column will contain two more numbers. In the example with a = 87 and b = 64, the penultimate column contains 34 and 25.
Step 8. Note that (87 * 25) - (64 * 34) = -1
The determinant of the 2x2 matrix in the lower right will always be either +1 or -1. If it is negative, multiply both sides of the equality by -1 to get - (87 * 25) + (64 * 34) = 1. This observation is the starting point from which to build a solution.
Step 9. Return to the original equation
Rewrite the equality from the previous step either in the form 87 * (- 25) + 64 * (34) = 1 or as 87 * (- 25) - 64 * (- 34) = 1, whichever is more similar to original equation. In the example, the second choice is preferable because it satisfies the term -64 y of the original equation when y = -34.
Step 10. Only now we have to consider the term c on the right side of the equation
Since the previous equation proves a solution for a x + b y = 1, multiply both parts by c to get a (c x) + b (c y) = c. If (-25, -34) is a solution of 87 x - 64 y = 1, then (-75, -102) is a solution of 87 x -64 y = 3.
Step 11. If a linear Diophantine equation has a solution, then it has infinite 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 of 87 x -64 y = 3, other solutions are (-11, -15), (53, 72), (117, 159) etc. The general solution can be written as (53 + 64 k, 72 + 87 k) where k is any integer.
Advice
- You should be able to do this with pen and paper as well, but when you're working with large numbers, a calculator, or better yet, a spreadsheet can be very useful.
- Check your results. The equality of step 8 should help you identify any mistakes made using Euclid's algorithm or in compiling the table. Checking the final result with the original equation should highlight any other errors.
