5. The least common multiple of the first positive integers

Prerequirements:

We know that a way to compute the least common multiple between two or more integer numbers is to decompose them into prime factors, and then taking each distinct prime factor with its greatest power in the considered numbers. Going on this way, the factorization of the least common multiple will result. For example, given the three numbers 4 = 2^2, 6 = 2 \cdot 3 and 45 = 3^2 \cdot 5, and computing their least common multiple, we see that the distinct prime factors are 2, 3 and 5; 2 appears with the greatest exponent 2 in 4, 3 appears with the greatest exponent 2 in 45, 5 appears with the greatest exponent 1 again in 45; so the least common multiple we are looking for is 2^2 \cdot 3^2 \cdot 5 = 180.

There exists a particularly interesting case in which the least common multiple can be computed through a reasoning, without decomposing the numbers into prime factors: it’s the computation of the least common multiple of the positive integer numbers up to a certain number x, that is \mathrm{LCM}(1, 2, \dots, x). Of course this expression coincides with \mathrm{LCM}(2, \dots, x) if x \geq 2, as in this case the number 1 does not give any contribution to the computation. This quantity, as function of x, is so important in number theory that it’s worth to indicate it with a specific notation:

Least common multiple of positive integer numbers up to x

We define the function:

\psi^{\star}(x) := \mathrm{LCM}(1, \dots, x)

where x > 0 is an integer number.

In order to compute \psi^{\star}(x) without an explicit decomposition into prime factors, let’s start to subdivide into two phases the method for computing the least common multiple we already know:

  1. Identification of prime numbers: we scan the factorizations of the given numbers and take note of the primes we find, ignoring repetitions;
  2. We search each prime p, found in the previous step, into the factorizations of the given numbers and take note of the maximum exponent it appears with: that will be the exponent of p in the final result.

In the case of numbers from 2 to x, it’s immediate to see that, scanning their factorizations, the only prime numbers we find are those less than or equal to x: so we have the answer for the first point. About the exponents, we have to ask ourselves: given a prime number p \leq x, what is the greatest exponent it can have in the factorizations of the numbers 2, \dots, x? It looks like a complex question, but it’s enough to observe that this exponent k cannot exceed \log_{p} x, because, by the definition of logarithm, we write \log_{p} x = k meaning that p^k = x; but then, being k an integer number, it cannot exceed \left \lfloor \log_p x \right \rfloor. Now let’s consider the integer number p^{\left \lfloor \log_p x \right \rfloor}. By contruction it’s less than or equal to x, so we have found a number, among those to compute the least common multiple of, in whose factorization p has exponent \left \lfloor \log_p x \right \rfloor. But we said that this is the greatest possible exponent for p, so we have found the greatest exponent required in the second point. Summarizing, we can state the following Proposition:

Computation of \psi^{\star}(x)

For every integer x > 0:

\psi^{\star}(x) = \prod_{p \leq x} p^{\left \lfloor \log_p x \right \rfloor} \tag{1}
We note that Proposition N.2 includes the case of x = 1, that we did not consider in the previous reasoning, but it can be immediately verified: in this case in fasct the least common multiple is 1, and it’s equal to the product of an empty set of prime numbers (this rule was introduced in the post The product of the first prime numbers: an overestimation).

Overestimations and underestimations

We can note an important thing looking at equation (1). In the exponent of p, \left \lfloor \log_p x \right \rfloor, it was necessary to use the integer part for the exact computation of \psi^{\star}(x), but, if we decide to disregard it, we have that

\psi^{\star}(x) = \prod_{p \leq x} p^{\left \lfloor \log_p x \right \rfloor} \leq \prod_{p \leq x} p^{\log_p x} = \prod_{p \leq x} x \tag{2}

it’s a product of factors all equal to x. But the number of factors, given by the condition p \leq x, is the number of primes less than or equal to x:

\prod_{p \leq x} x = \underbrace{x \cdot \dots \cdot x}_{|\{\textrm{prime numbers } \leq x\}| \textrm{ times}} = x^{|\{\textrm{prime numbers } \leq x\}|} \tag{3}

The quantity at the exponent, appearing here for the first time, is of central importance in number theory, therefose we give a definition for it:

Definition N.6 (Number of primes less that or equal to x)

We define the function

\pi(x) := |\{\textrm{prime numbers} \leq x\}|

where x is a positive integer.

Starting from equations (2) and (3), using Definition N.6, we obtain the following overestimation of the \psi^{\star} function:

Overestimation of \psi^{\star}(x) with \pi(x)

For every integer x > 0:

\psi^{\star}(x) \leq x^{\pi(x)}

We can also obtain an underestimation of the \psi^{\star} function, starting from Lemma N.1 we encountered in the path towards Bertrand’s postulate. This Lemma is a property of the factorization of a particular number: the binomial \binom{2n}{n}. It states that, in the factorization of this number, a prime number p cannot have an exponent greater than \log_p 2n. But, being the exponent of p an integer number, this is equivalent to say that it cannot be greater than \left \lfloor \log_p 2n \right \rfloor. We can express this concept with the followinf formula:

\binom{2n}{n} \leq \prod_{p \mid \binom{2n}{n}} p^{\left \lfloor \log_p 2n \right \rfloor}

where the product is extended to all the prime factors of the binomial. But, as a consequence of the definition of the binomial \binom{2n}{n}, as we observed at the beginning of the post about Bertrand’s postulate, its prime factors cannot be greater than 2n, so we can extend the product by considering all the primes less than or equal to 2n, getting back in touch with Proposition N.2:

\binom{2n}{n} \leq \prod_{p \mid \binom{2n}{n}} p^{\left \lfloor \log_p 2n \right \rfloor} \leq \prod_{p \leq 2n} p^{\left \lfloor \log_p 2n \right \rfloor} = \psi^{\star}(2n) \tag{4}

This inequality is an underestimation of \psi^{\star}(2n), that is of \psi^{\star}(x) when x is even. Now we have to:

  • Extend it to the case of even x;
  • Eliminate the binomial, for making the formula more suitable to be treatable by the tools of asymptotic analysys.

Operating this way, the following inequality is obtained:

Underestimation of \psi^{\star}(x)

For every integer x > 0:

\psi^{\star}(x) \geq \sqrt[3]{2^x}

It will let us, already in the next post, to obtain a theorem surprisingly similar to the prime number Theorem.

About the elimination of the binomial, in view of using the tools of asymptotic analysis, it’s convenient to begin with as simple as possible functions right now. So let’s use Property N.3, obtaining that \sqrt{2^{2n}} \leq \binom{2n}{n}, where the first term is simplified to 2^n, so

2^n \leq \binom{2n}{n} \tag{5}

Connecting (4) with (5) we obtain

2^n \leq \psi^{\star}(2n) \tag{6}

Now if x is even we can set 2n := x and substitute it into (6), obtaining:

2^{\frac{x}{2}} \leq \psi^{\star}(x), x \textrm{ even} \tag{7}

From Definition N.5 we can note that \psi^{\star} function is strictly increasing, that is

\psi^{\star}(x - 1) \lt \psi^{\star}(x), \forall x \geq 2 \tag{8}

where the limitation x \geq 2 is necessary in order to let the argument of \psi^{\star}(x - 1) be at least 1, as the definition requires. If in (8) we suppose x odd (and in particular x \geq 3, given the limitation), certainly x - 1 is even, so we can use (7) with x - 1 in place of x, so extending (8):

2^{\frac{x - 1}{2}} \leq \psi^{\star}(x - 1) \lt \psi^{\star}(x) \tag{9}

This holds for all odd x greater or equal to 3. Among the possible odd xs, only the case of x = 1 is excluded, and we’ll discuss it separately.
Combining (9), that holds for odd integers greater or equal than 3, with (7), that holds for even numbers, we can write:

2^{\left \lfloor \frac{x}{2} \right \rfloor} \leq \psi^{\star}(x), \forall x \geq 2

In fact \left \lfloor \frac{x}{2} \right \rfloor is equal to \frac{x}{2} if x is even; \frac{x - 1}{2} if x is odd.
The integer part can be inconvenient in calculations, so it’s worth to eliminate it, by observing for example that \left \lfloor \frac{x}{2} \right \rfloor \geq \frac{x}{3} for every x \geq 2. So the left side term can be in turn underestimated with 2^{\frac{x}{3}} = \sqrt[3]{2^x}:

\sqrt[3]{2^x} = 2^{\frac{x}{3}} \leq 2^{\left \lfloor \frac{x}{2} \right \rfloor} \leq \psi^{\star}(x), \forall x \geq 2 \tag{10}

Finally we have to examine the case x = 1, for which (10) still holds: in fact \sqrt[3]{2} \leq \psi^{\star}(1) = 1. So (10) holds indeed for every possible x, as stated by Proposition N.3

Connection with the \theta^{\star}(x) function

Let’s compare (1) with the definition of the \theta^{\star}(x) function:

\theta^{\star}(x) := \prod_{p \leq x} p

The difference is in the exponents of the primes p, that in \theta^{\star}(x) are always 1, whereas in \psi^{\star}(x) depend on x. Actually the two functions are tightly interconnected, and it’s important to establish exactly how.

First, the product (1) that defines \psi^{\star}(x), with a bit of creativity can be seen as the product of the columns of a certain table. Starting then from this table, but multiplying its rows instead of its columns, the same result is obtained (again \psi^{\star}(x)), but in a different form. This argument, that we invite you to read in detail, gives the name to the following Lemma:

Reformulation of \psi^{\star}(x) (“calculation by rows”)

For every integer x > 0:

\psi^{\star}(x) = \left(\prod_{p \leq x} p\right) \cdot \left(\prod_{p^2 \leq x} p\right) \cdot \dots \cdot \left(\prod_{p^R \leq x} p\right) \tag{13}

where R := \left \lfloor \log_2 x \right \rfloor.

In (1), the prime p has exponent \left \lfloor \log_p x \right \rfloor. This is, as we observed initially, the exponent of the greatest integer power of p less than or equal to x. Let’s try to analyze these powers, as p changes, with the help of a table. For every p we consider the column p^{\left \lfloor \log_p x \right \rfloor} and write p at the intersection with row i = 1, 2, 3, \dots if and only if i \leq \left \lfloor \log_p x \right \rfloor, that is p^i \leq x. For example, if x = 17 we have that:

  • If p = 2, the greatest power of p less than or equal to 17 is 16 = 2^4, so we write 2 at the intersection between column 16 and rows 1, 2, 3 and 4;
  • If p = 3, the greatest power of p less than or equal to 17 is 9 = 3^2, so we write 3 at the intersection between column 9 and rows 1 and 2;
  • If p = 5, the greatest power of p less than or equal to 17 is 5 = 5^1, so we write 5 at the intersection between column 5 and row 1;

Going on this way the following table is obtained:

Table 1: greatest numbers less than or equal to 17 that are powers of prime numbers
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17
1 0 0 0 0 5 0 7 0 3 0 11 0 13 0 0 2 17
2 0 0 0 0 0 0 0 0 3 0 0 0 0 0 0 2 0
3 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 2 0
4 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 2 0

We can note that (1) is the product of the nonzero nonbers in this table, computed by columns:

\psi^{\star}(17) =
\prod_{p \leq 17} p^{\left \lfloor \log_p 17 \right \rfloor} =
2^4 \cdot 3^2 \cdot 5 \cdot 7 \cdot 11 \cdot 13 \cdot 17 =
5 \cdot 7 \cdot 3^2 \cdot 11 \cdot 13 \cdot 2^4 \cdot 17 =
C_5 \cdot C_7 \cdot C_9 \cdot C_{11} \cdot C_{13} \cdot C_{16} \cdot C_{17}

where C_j is the product of numbers in column j. In the end we have the product of the nonzero numbers of all “filled” columns, that is containing at least a nonzero number. So we can say that Table 1 is just an alternative way to write the least common multiple of the positive integers less that or equal to 17, as you can see in the following picture:

Figure 1: Least common multiple of the integers from 1 to 17, written in a tabular form, of which we study the product by columns and the product by rows

With the help of Table 1 we can compute the same product, but proceeding by rows. Indicating with R_i the product of nonzero numbers of row i, we have:

\psi^{\star}(17) =
(2 \cdot 3 \cdot 5 \cdot 7 \cdot 11 \cdot 13 \cdot 17) \cdot (2 \cdot 3) \cdot 2 \cdot 2 =
R_1 \cdot R_2 \cdot R_3 \cdot R_4 \tag{11}

But what are R_1, R_2, R_3, R_4? We said that a prime p appears in row i if and only if p^i \leq x; moreover if it appears there, because of the way we constructed the table, it does only once. So in row 1 all and only the primes less than or equal to x appear, in row 2 all and only the primes p such that p^2 \leq x, and so on. Therefore (11) can be developed in this way:

\psi^{\star}(17) = \left(\prod_{p \leq 17} p\right) \cdot \left(\prod_{p^2 \leq 17} p\right) \cdot \left(\prod_{p^3 \leq 17} p\right) \cdot \left(\prod_{p^4 \leq 17} p\right) \tag{12}

The argument carried on for x = 17 holds for any x; it remains just to understand how computing the number of rows of the table as a function of x. Given the way we constructed the table, for every prime p we write in rows 1, 2, \dots, \left \lfloor \log_p x \right \rfloor. So the last table row in which we write at least once is the greatest possible value of \left \lfloor \log_p x \right \rfloor, as p varies. But this quantity increases as p decreases, so the maximum we are looking for is in general \left \lfloor \log_2 x \right \rfloor (for x = 17 we have, as we expect, \left \lfloor \log_2 17 \right \rfloor = 4).

Summarizing, we can generalize (12) and state Lemma N.2.

Starting from (13), it’s easy to establish the connection between \psi^{\star} and \theta^{\star} functions. First of all the first factor of the product, \prod_{p \leq x} p, is just \theta^{\star}(x). About the second factor, the condition p^2 \leq x is equivalent to p \leq \sqrt{x}, so \prod_{p^2 \leq x} p = \prod_{p \leq \sqrt{x}} p = \theta^{\star}(\sqrt{x}). We can reason in a similar way for the other factors, up to \prod_{p^R \leq x} p = \prod_{p \leq \sqrt[R]{x}} p = \theta^{\star}(\sqrt[R]{x}). So we can express the connection between the two functions with the following Proposition:

Connection between \psi^{\star} and \theta^{\star} functions

For every integer x > 0:

\psi^{\star}(x) = \theta^{\star}(x) \cdot \theta^{\star}(\sqrt{x}) \cdot \dots \cdot \theta^{\star}(\sqrt[R]{x})

where R := \left \lfloor \log_2 x \right \rfloor.

Leave a Reply

Your email address will not be published.