Least common multiple

In arithmetic and number theory the least common multiple or lowest common multiple (lcm) or smallest common multiple 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, e.g., if a = 0 or b = 0, 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

<math>{2\over21}+{1\over6}={4\over42}+{7\over42}={11\over42},<math>

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

If a and b are not both zero, the least common multiple can be computed by using the greatest common divisor (gcd) of a and b:

<math>\operatorname{lcm}(a,b)=\frac{a\cdot b}{\operatorname{gcd}(a,b)}.<math>

Thus, the Euclidean algorithm for the gcd also gives us a fast algorithm for the lcm. To return to the example above,

<math>\operatorname{lcm}(21,6)={21\cdot6\over\operatorname{gcd}(21,6)}={126\over3}=42.<math>

Efficient calculation

The formula

<math>\operatorname{lcm}(a,b)=\frac{(a\cdot b)}{\operatorname{gcd}(a,b)}<math>

is adequate to calculate the lcm for small numbers using the formula as written.

Because that (ab)/c = a(b/c) = (a/c)b, one can calculate the lcm using the above formula more efficiently, by firstly exploiting the fact that b/c or a/c may be easier to calculate than the quotient of the product ab and c. This can be true whether the calculations are performed by a human, or a computer, which may have storage requirements on the variables a, b, c, where the limits may be 4 byte storage - calculating ab may cause an overflow, if storage space is not allocated properly.

Using this, we can then calculate the lcm by either using:

<math>\operatorname{lcm}(a,b)=\left({a\over\operatorname{gcd}(a,b)}\right)\cdot b<math>

or

<math>\operatorname{lcm}(a,b)=a\cdot\left({b\over\operatorname{gcd}(a,b)}\right)\;.<math>

Done this way, the previous example becomes:

<math>\operatorname{lcm}(21,6)={21\over\operatorname{gcd}(21,6)}\cdot6={21\over3}\cdot6=7\cdot6=42.<math>