How to solve linear Diophantine equations( These equations have integer coefficients and are of the form: ax + by = c ) using Euclid's algorithm ??? asked 14 Nov '14, 11:20

If your equations are of type ax+by=c then you must have two equations to be able to solve them. Say you have two equations as ax+by=c and mx+ny=k, then you can write it in matrix form as,  a b   x  =  c   m n   y   k  Now reduce this matrix to Echelon form that means, do some row transformation so that m reduces to 0. To reduce m to zero we will find GCD of a and m by Euclid's algorithm. Say CGD(a,m) = g. Do R1 = R1 * g/a and then R2 = R2  R1 * m/g. This will reduce your system to Echelon form. and now it is very easy to find x and y. Pseudo code:
link
This answer is marked "community wiki".
answered 14 Nov '14, 13:33
