Least common multiple

Given two positive natural numbers \(a\) and \(b\), their least common multiple \(\text{LCM}(a,b)\) is the smallest natural number divided by both \(a\) and \(b\). As an example take \(a=12, b=10\), then the smallest number divided by both of them is \(60\).

There is an equivalent definition of the LCM, which is strange at first glance but turns out to be mathematically much more suited to generalisation: the LCM \(l\) of \(a\) and \(b\) is the natural number such that for every number \(c\) divisible by both \(a\) and \(b\), we have \(l\) divides \(c\). This describes the LCM as a poset least upper bound (namely the partially ordered set \(\mathbb{N}\) under the relation of divisibility).

Note that for \(a\), \(b\) given, their product \(ab\) is a natural number divided by both of them. The least common multiple \(\text{LCM}(a,b)\) divides the product \(ab\) and for \(\text{GCD}(a,b)\) the greatest common divisor of \(a, b\) we have the formula

$$a\cdot b = \text{GCD}(a,b) \cdot \text{LCM}(a,b). $$
This formula offers a fast way to compute the least common multiple: one can compute \(\text{GCD}(a,b)\) using the euclidean algorithm and then divide the product \(ab\) by this number.

In practice, for small numbers \(a,b\) it is often easier to use their factorization into prime numbers. In the example above we have \(12=2 \cdot 2 \cdot 3\) and \(10=2 \cdot 5\), so if we want to build the smallest number \(c\) divided by both of them, we can take \(60=2 \cdot 2 \cdot 3 \cdot 5\). Indeed, to compute \(c\) look at each prime number \(p\) dividing one of \(a,b\) (in the example \(p=2,3,5\)). Then writing \(c\) as a product we take the factor \(p\) the maximal number of times it appears in \(a\) and \(b\). The factor \(p=2\) appears twice in \(12\) and once in \(10\), so we take it two times. The factor \(3\) appears once in \(12\) and zero times in \(10\), so we only take it once, and so on.

Parents:

  • Mathematics

    Mathematics is the study of numbers and other ideal objects that can be described by axioms.