# Least common multiple

The

**least common multiple** (LCM) of two

integers *a* and

*b* is the smallest positive integer that is a multiple of both

*a* and

*b*. If there is no such positive integer, i.e., if either

*a* or

*b* is zero,
then lcm(

*a*,

*b*) is defined to be zero.

The least common multiple is useful when adding or subtracting fractions, because it yields the lowest common denominator. Consider for instance

- 2/21 + 1/6 = 4/42 + 7/42 = 11/42

the denominator 42 was used because lcm(21,6) = 42.

In case not both *a* and *b* are zero, the least common multiple can be computed by using the greatest common divisor (or GCD) of *a* and *b*,

| *a* *b* |

lcm(*a*, *b*) = | --------- |

| gcd(*a*, *b*) |

Thus, the

Euclidean algorithm for the GCD also gives us a fast

algorithm for the LCM. As an example, the LCM of 12 and 15 is 12 × 15 / 3 = 60.