# 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

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.