Euclidean Algorithm Approach
To Diophantine Equations
S. McAdams, S. Pinion, L. Stueve
Begin with the equation 199d - 98c = -5
Take the two variable coefficients 199 & -98 and find the greatest common
divisor. To do this
1) divide 199 by 98, this results in the equation (2 * 98) + 3 = 199 .
2) divide 98 by 3, this results in the equation (32*3) +2 = 98
3) divide 3 by 2, this results in the equation (1 * 2) + 1 = 3
4) divide 2 by 1, this results in the equation (1 * 2) = 2, resulting in
a greatest common
divisor of 1.
In each of these equations the quantity added represents the remainder of
the division equation. The greatest common divisior is attained once the
remainder is zero from this repeated division algorithm.
Rewrite the equations setting them equal to the remainders
1) 3 = 199 - (2 * 98)
2) 2 = 98 - (32 * 3)
3) 1 = 3 - (1*2)
Use the above equations to write the last equation 1 = 3 - (1 * 2) in
terms of the original coefficients -- [ -98 & 199].
a) 1 = 3 - 1 * (98 -(32 * 3) ) which simplifies to 1 = (33 * 3 ) - 98
b) therefore, 1 = 33 (199 - (98 * 2)) - 98 which simplifies to 1 = (33 *
199) - (98 * 67)
This gives the solution of d = 33, and c = 67 --- This is not an
accurate solution. When you put 33 & 67 into the original equation
you end up with 199 (33) - 98(67) = 1, we need the equation to be equal
to -5. I am still not sure where my error is in the euclidean approach
to these diophantine equations, however this helped us narrow down the field
for the spreadsheet considerably so that we found an accurate solution.
To return to Check Problem, and an accurate solution, click 8B>here.