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

Parents:

• Mathematics

Mathematics is the study of numbers and other ideal objects that can be described by axioms.