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 $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.