Given two positive natural numbers and $b$ , their least common multiple $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 $N$ under the relation of divisibility).

Note that for $a$ , $b$ given, their product $a b$ is a natural number divided by both of them. The least common multiple $LCM (a, b)$ divides the product $a b$ and for $GCD (a, b)$ the greatest common divisor of $a, b$ we have the formula $a \cdot b = GCD (a, b) \cdot LCM (a, b) .$ This formula offers a fast way to compute the least common multiple: one can compute $GCD (a, b)$ using the Euclidean_algorithm and then divide the product $a b$ 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.

Posts

Wikitag Contributions

Comments