Least common multiple

[summary: The least common multiple (LCM) of two positive natural numbers a, b is the smallest natural number that both a and b divide, so for instance LCM(12,10) = 60.]

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.