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.

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}}Thusthesmallestcommonmultipleof63and77is693.Butthisbrute-forceapproachtocomputingthesmallestcommonmultipleisnotefficient.$

[ to be continued ... ]