Least common multiple

https://arbital.com/p/least_common_multiple

by Johannes Schmitt Sep 24 2016 updated Sep 25 2016


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