 Euclid's algorithm.

#1

How to solve linear Diophantine equations( These equations have integer coefficients and are of the form:
ax + by = c ) using Euclid’s algorithm ???

#2

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:

``````solveSystem()
{
// Input equations and store them in 2*3 array
// Out of which first two columns store x and y coefficients
// and last columns store values of c and k.
int[][] eq = new int;
takeInput(eq);

int g = gcd(eq,eq); //Use Euclid's algorithm to implement gcd function.
//Change R1.
for(int j=0; j<3; j++)
eq[j]*=g/eq;
//Change R2.
for(int j=0; j<3; j++)
eq[j]-= eq[j]*eq/g;
//Now your eq matrix is in Echelon form.
output: y = eq/eq;
output: x = (eq - y* eq)/eq;
}``````