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.