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.