Least common multiple

The least common multiple (often abbreviated lcm, or l.c.m.) of two or more natural numbers is the smallest number which is a multiple of (i.e., is divided evenly by) both (or all) the numbers. Since the product of the numbers is a multiple of each of the numbers, and since a multiple of a number is greater than the number, the least common multiple of some numbers is a number between the greatest of these numbers and their product (inclusive), and it therefore can be determined (at least in principle) by testing finitely many numbers.

The least common multiple of two numbers equals their product if and only if their greatest common divisor is 1, i.e., if they are relatively prime. The least common multiple of three or more numbers equals their product if and only if they are pairwise relatively prime.

The least common multiple of two numbers a and b usually is written as lcm(a,b), or, if no confusion is to be expected, simply as [a,b].

Finding the least common multiple

A theoretically important method to determine the least common multiple uses prime factorization: Every prime factor of one of the numbers must be a prime factor of the least common multiple. The least common multiple therefore is the product of all prime factors taken with the highest power occurring in one of the numbers. However, since prime factorization is not efficient, this is at most practical for small numbers (or for numbers whose factorization is already known). This product expression shows that the least common multiple can be characterized by the following property: The lcm is a common multiple, and it divides evenly every common multiple.

In order to efficiently calculate the least common multiple of two numbers, first determine the greatest common divisor (using the Euclidean algorithm) and then use

lcm(a,b) = ab/gcd(a,b).

The least common multiple can be calculated by repeating this:

lcm(a,b,c) = lcm(a,lcm(b,c))

Examples

For instance,

lcm(4,9)=36, lcm(4,6)=12, and lcm(4,12)=12,

for 72 =2.2.2.3.3, 108 =2.2.3.3.3 there is lcm(72,108) = 2.2.3.3 = 432,

for 6 =2.3, 10 =2.5, 15 =3.5 there is lcm(6,10,15) = 30.

Applications

In elementary arithmetic, the least common multiples used when adding fractions.

Formulas

$\max(a,b)\leq \mathop {\rm {lcm}} (a,b)\leq ab$

$\mathop {\rm {gcd}} (a,b)\mathop {\rm {lcm}} (a,b)=ab$

If

$a=\prod _{p\ {\rm {prim}}}p^{a(p)}\ {\textrm {and}}\ b=\prod _{p\ {\rm {prim}}}p^{b(p)}$

then

$\mathop {\rm {lcm}} (a,b)=\prod _{p\ {\rm {prim}}}p^{\max(a(p),b(p))}$