Given two positive natural numbers and , their least common multiple is the smallest natural number divided by both and . As an example take , then the smallest number divided by both of them is .
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 of and is the natural number such that for every number divisible by both and , we have divides . This describes the LCM as a poset least upper bound (namely the partially ordered set under the relation of divisibility).
Note that for , given, their product is a natural number divided by both of them. The least common multiple divides the product and for the greatest common divisor of we have the formula This formula offers a fast way to compute the least common multiple: one can compute using the Euclidean_algorithm and then divide the product by this number.
In practice, for small numbers it is often easier to use their factorization into prime numbers. In the example above we have and , so if we want to build the smallest number divided by both of them, we can take . Indeed, to compute look at each prime number dividing one of (in the example ). Then writing as a product we take the factor the maximal number of times it appears in and . The factor appears twice in and once in , so we take it two times. The factor appears once in and zero times in , so we only take it once, and so on.