Algorithm for Computing the LCM

Let M^k = max x_i^(k). There are only finitely many k such that M^k ≤ L. Let m be the largest such index. I.e., we assume that M^m ≤ L whereas M^m+1 > L provided the algorithm does not stop at step m. This assumption leads to a contradiction.

Indeed, by a suitable re-numbering, we will then have

with r a positive integer and

Now (r+l)·x₁ ≤ L would imply that M^m+1 ≤ L which could not be, by the maximality of m. Hence

But this contradicts the fact that L is a multiple of x₁. Hence the assumption that m is not the last step is false and

But then M^m is a common multiple of all the x_i, i = 1, 2, ..., n, and L ≥ M^m, at that. However, since L is the least common multiple, L ≤ M^m. Hence

and

as required.

Remark

This algorithm could be used to simulate a multitasking environment. In fact it was so used in the early days of computing. Assume, for example, you write a program which shows several balls bouncing up and down and off the walls. A task is associated with each ball that regularly updates its position and velocity. All balls must be continuously controlled, i.e. all the associated tasks need to be executed on a rotating basis. In addition, some balls may have to be updated more frequently than others.

The solution is this: each task k is assigned the (reversed) relative frequency x_k and the LCM algorithm is run. One step of task k is executed whenever x_k^(m) is updated. The above discussion shows that all tasks will be updated with the required frequencies.

It's not hard to imagine why the algorithm is thought to resemble a patch of growing onions which are cut individually when they reach a prescribed height. Indeed in networking there is an important Onion Routing algorithm. In computational geometry, a similar idea led to the Onion Peeling Algorithm.

Reference

1. A. J. Goldman; N. J. Fine, El655, The American Mathematical Monthly, Vol. 71, No. 9. (Nov., 1964), pp. 1045-1046.