GCD and LCM

GCD (Greatest Common Divisor) of two non-zero integers, is the largest positive integer that divides both numbers without remainder. For example, the GCD of the number 10 and 25 is 5 (10 = 5*2 and 25 = 5*5).

LCM (Least Common Multiple) of two integers a and b is the smallest positive integer that is a multiple of both a and b. Since it is a multiple, a and b divide it without remainder. If there is no such positive integer, e.g., if a = 0 or b = 0, then LCM is defined to be zero.

There is a connection between GCD and LCM and here it is: GCD(a, b) * LCM(a, b) = a*b

I will show you a simple implementation of the Euclid’s algorithm to determine the GCD of two integers. After you find the GCD of those two integers, you can find the LCM of them, too.