Suppose we have to find the the gcd of twoo numbers a,b.
if a > b
then it follows:
a = b*q+r
where q = quotient and r is remainder.Now r must be smaller than b.
i.e.
b = r*q1 + r1, similarly
r = r1*q2 + r2
.....
.....
since remainder decreases with every step which at one time leads to 0.
i.e.
r(n-2)= r(n-1)*qn + rn, where rn = 0.
the final non-zero remainder will be the gcd of a,b which is r(n-1)
algorithm
GCD(a,b)
IF (b == 0) return a;
ELSE
return GCD(b, a/b);
