# Least common multiple

Given two pos­i­tive nat­u­ral num­bers $$a$$ and $$b$$, their least com­mon mul­ti­ple $$\text{LCM}(a,b)$$ is the small­est nat­u­ral num­ber di­vided by both $$a$$ and $$b$$. As an ex­am­ple take $$a=12, b=10$$, then the small­est num­ber di­vided by both of them is $$60$$.

There is an equiv­a­lent defi­ni­tion of the LCM, which is strange at first glance but turns out to be math­e­mat­i­cally much more suited to gen­er­al­i­sa­tion: the LCM $$l$$ of $$a$$ and $$b$$ is the nat­u­ral num­ber such that for ev­ery num­ber $$c$$ di­visi­ble by both $$a$$ and $$b$$, we have $$l$$ di­vides $$c$$. This de­scribes the LCM as a poset least up­per bound (namely the par­tially or­dered set $$\mathbb{N}$$ un­der the re­la­tion of di­visi­bil­ity).

Note that for $$a$$, $$b$$ given, their product $$ab$$ is a nat­u­ral num­ber di­vided by both of them. The least com­mon mul­ti­ple $$\text{LCM}(a,b)$$ di­vides the product $$ab$$ and for $$\text{GCD}(a,b)$$ the great­est com­mon di­vi­sor of $$a, b$$ we have the for­mula

$$a\cdot b = \text{GCD}(a,b) \cdot \text{LCM}(a,b).$$
This for­mula offers a fast way to com­pute the least com­mon mul­ti­ple: one can com­pute $$\text{GCD}(a,b)$$ us­ing the eu­clidean al­gorithm and then di­vide the product $$ab$$ by this num­ber.

In prac­tice, for small num­bers $$a,b$$ it is of­ten eas­ier to use their fac­tor­iza­tion into prime num­bers. In the ex­am­ple above we have $$12=2 \cdot 2 \cdot 3$$ and $$10=2 \cdot 5$$, so if we want to build the small­est num­ber $$c$$ di­vided by both of them, we can take $$60=2 \cdot 2 \cdot 3 \cdot 5$$. In­deed, to com­pute $$c$$ look at each prime num­ber $$p$$ di­vid­ing one of $$a,b$$ (in the ex­am­ple $$p=2,3,5$$). Then writ­ing $$c$$ as a product we take the fac­tor $$p$$ the max­i­mal num­ber of times it ap­pears in $$a$$ and $$b$$. The fac­tor $$p=2$$ ap­pears twice in $$12$$ and once in $$10$$, so we take it two times. The fac­tor $$3$$ ap­pears once in $$12$$ and zero times in $$10$$, so we only take it once, and so on.

Parents:

• Mathematics

Math­e­mat­ics is the study of num­bers and other ideal ob­jects that can be de­scribed by ax­ioms.