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.