To solve a Diophantine equation, find integer solutions to a given equation. This requires the use of a Euclidean algorithm worked from top to bottom and back up.
- Adjust the equation
Adjust the equation to the following form: ax + by = c. For this form, "a," "b" and "c" are all integers.
- Use the Euclidean algorithm
Use the Euclidean algorithm to set up a system of equations. For these equations, a = r1 and b = r2. The variation for Diophantine equations uses the following algorithms: r1 = q1r2 + r3, r2 = q2r3 + r4, r(n-3) = q(n-3)r(n-3) + r(n-1), r(n-2) = q(n-2)r(n-1) +1. It may be necessary to use additional algorithms depending on the problem. In these algorithms, "n" represents the step number.
- Rearrange the algorithms
Rearrange the bottom two algorithms, and begin to use substitution. For example, rearrange the bottom two algorithms to get the following: 1 = r(n-2) - q(n-2)r(n-1) and r(n-1) = r(n-3) - q(n-3)r(n-3). Continue this process until you reach the top algorithm.
- Insert the values and solve
Insert the values from the original equation, and solve the equation. The answers appear in the top algorithm. Be sure to solve the original algorithms prior to going back up through the substituted ones.