Least common multiple/Student Level

In arithmetic, the least common multiple (LCM or lcm) or smallest common multiple of several integers is the smallest integer that is a multiple of all of them.

For example, the smallest common mutliple of 9 and 12 is 36. Since

36 = 12 × 3, and

36 = 2 × 4,

36 is indeed a multiple of both 9 and 12. Moreover it is the smallest mutliple that 9 and 12 have in common.

One use of the smallest common mutliple is as the smallest common denominator when adding, subtracting, or comparing fractions:

${\frac {5}{12}}+{\frac {7}{9}}={\frac {5\times 3}{12\times 3}}+{\frac {7\times 4}{9\times 4}}={\frac {15}{36}}+{\frac {28}{36}}={\frac {15+28}{36}}={\frac {43}{36}}.$

A simple theoretical question and a primitive algorithm

A simple theoretical question is whether two integers must have any multiples in common. Imagine that we begin lists of the multiples of two integers, e.g. 63 and 77:

${\begin{matrix}63\times 1&=&63&&&&77\times 1&=&77\\63\times 2&=&126&&&&77\times 2&=&154\\63\times 3&=&189&&&&77\times 3&=&231\\63\times 4&=&252&&&&77\times 4&=&308\\63\times 5&=&315&&&&77\times 5&=&385\\63\times 6&=&378&&&&77\times 6&=&462\\63\times 7&=&441&&&&77\times 7&=&539\\63\times 8&=&504&&&&&\cdot \\&\vdots &&&&&&\vdots \end{matrix}}$

One could wonder whether the two lists might continue forever without any number appearing in both lists. Before addressing that, let us note in the interest of simplicity that we need not perform a mutliplication at each step in extending the list; we need only add:

${\begin{matrix}63&&&&&&&77\\&\downarrow \ \mathrm {add} \ 63&&&&&&&\downarrow \ \mathrm {add} \ 77\\126&&&&&&&154\\&\downarrow \ \mathrm {add} \ 63&&&&&&&\downarrow \ \mathrm {add} \ 77\\189&&&&&&&231\\&\downarrow \ \mathrm {add} \ 63&&&&&&&\downarrow \ \mathrm {add} \ 77\\252&&&&&&&308\\&\downarrow \ \mathrm {add} \ 63&&&&&&&\downarrow \ \mathrm {add} \ 77\\315&&&&&&&385\\&\downarrow \ \mathrm {add} \ 63&&&&&&&\downarrow \ \mathrm {add} \ 77\\378&&&&&&&462\\\vdots &&&&&&&\vdots \end{matrix}}$

Could the lists continue forever without any number appearing in both? The answer is that the 77th number in the first list must be equal to the 63rd number in the second list, since both are equal to 63 × 77 = 4851. But that need not be the first number appearing in both lists. It is a common multiple of 63 and 77, but as we shall see, it is not the smallest common multiple. Continuing the list only slightly further we get this:

${\begin{matrix}63\times 1&=&63&&&&77\times 1&=&77\\63\times 2&=&126&&&&77\times 2&=&154\\63\times 3&=&189&&&&77\times 3&=&231\\63\times 4&=&252&&&&77\times 4&=&308\\63\times 5&=&315&&&&77\times 5&=&385\\63\times 6&=&378&&&&77\times 6&=&462\\63\times 7&=&441&&&&77\times 7&=&539\\63\times 8&=&504&&&&77\times 8&=&616\\63\times 9&=&567&&&&77\times 9&=&693\\63\times 10&=&630&&&&&\cdot \\63\times 11&=&693&&&&&\cdot \\&\vdots &&&&&&\vdots \end{matrix}}$

Thus the smallest common multiple of 63 and 77 is 693.

More sophisticated algorithms

But this brute-force approach to computing the smallest common multiple is not efficient. A more efficient method uses prime factorizations. Consider the factorizations of 63 and 77 into prime numbers:

63 = 3 × 3 × 7,

77 = 7 × 11.

In any common multiple of 63 and 77, each prime factor must occur at least as many times as it does in either 63 or 77. Thus we need at least two 3s, at least one 7, and at least one 11. If we have only that many of each factor, then the common multiple that we get is the smallest possible:

3 × 3 × 7 × 11 = 693.

[ to be continued ... ]