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.

Prime factorizations

One 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.

Now consider the problem of finding the smallest common multiple of 6600, 3276, and 7938. We begin by completely factoring each of these numbers:

6600 = 2 × 2 × 2 × 3 × 5 × 5 × 11,

3276 = 2 × 2 × 3 × 3 × 7 × 13,

7938 = 2 × 3 × 3 × 3 × 3 × 7 × 7.

We need:

• three 2s (since that many occur in the factorization of 6600);
• four 3s (since that many occur in the factorization of 7938);
• two 5s (since that many occur in the factorization of 6600);
• two 7s (since that many occur in the factorization of 7938);
• one 11 (since that many occur in the factorization of 6600);
• one 13 (since that many occur in the factorization of 3276).

We get

2³ × 3⁴ × 5² × 7² × 11 × 13 = 113513400.

The is the smallest common multiple of 6600, 3276, and 7938.

[ to be continued ... ]