GCD & LCM

GCD: Greatest Common Divisor:

int GCD(int a, int b)
{
    if (b==0) return a;
    return GCD(b,a%b);
}


int LCM(int a, int b)
{
   return b*a/GCD(a,b);
}

Euclid's algorithm can be used to solve linear Diophantine equations. These equations have integer coefficients and are of the form:

ax + by = c