Lowest Common Multiple

The lowest common multiple (LCM) of a finite set of non-zero integers is the smallest positive number that is a multiple of each integer in the set. It is a fundamental concept in number theory, and is closely related to the greatest common divisor. It is taught to elementary school students as an aid in adding fractions: to simplify \( \frac{a}{x}+\frac{b}{y}, \) one first writes the fractions with a common denominator, which is the LCM of \(x\) and \(y.\)

Simplify \( \frac1{105} + \frac1{50}.\)

---

Since \( \text{lcm}(105,50) = 1050,\) this sum can be rewritten as \( \frac{10}{1050} + \frac{21}{1050} = \frac{31}{1050}.\) \(_\square\)

Find the lcm of \( 30\) and \(36.\)

---

Here is a list of the positive multiples of each number:

\[ \begin{align} 30: &30,\ 60,\ 90,\ 120,\ 150,\ 180, \ldots \\\\ 36: &36,\ 72,\ 108,\ 144,\ 180, \ldots. \end{align} \]

The first number that appears on both lists is \( 180.\) \(_\square\)

The LCM is important in many applications of elementary number theory, including the Chinese remainder theorem, where \( \text{lcm}(a,b)\) appears as the modulus of the unique solution to a system of equations modulo \(a\) and \(b.\)

The LCM in the introduction was computed by listing the multiples of each number and searching for the first integer on every list. (The LCM always exists because the product of a list of numbers is divisible by each of the numbers in the list.) This is a very ineffective way of computing the LCM in general.

However, if the prime factorization of the numbers is known, then computing the least common multiple is much simpler. The primes in the factorization of the LCM are the primes that appear in the factorizations of at least one member of the list, and their exponent is the maximum of the exponents that appear in the individual factorizations.

Compute \(\text{lcm}(4200,3780,3528)\) using prime factorizations.

---

We have

\[ \begin{align} 4200 &= 2^3 \cdot 3 \cdot 5^2 \cdot 7 \\ 3780 &= 2^2 \cdot 3^3 \cdot 5 \cdot 7 \\ 3528 &= 2^3 \cdot 3^2 \phantom{\cdot 5 \cdot} \cdot 7^2. \end{align} \]

The LCM can be read off from these factorizations by taking the maximum exponent for each prime: \( 2^3 \cdot 3^3 \cdot 5^2 \cdot 7^2 = 264600.\) \(_\square\)

Generalizing this example, if the prime factorizations of \(a\) and \(b\) are

\[\begin{align} a & = p_1 ^{\alpha_1} p_2 ^{\alpha_2} \ldots p_k ^{\alpha_k} \\\\ b & = p_1 ^{\beta_1} p_2 ^ {\beta_2} \ldots p_k ^ {\beta_k}, \\ \end{align} \]

where the \( p_i\) are distinct primes and the \(\alpha_i\) and \( \beta_i\) are nonnegative integers, then

\[ \mbox{lcm}(a,b) = p_1 ^{\max(\alpha_1, \beta_1)} p_2 ^{\max(\alpha_2, \beta_2)} \ldots p_k ^{\max(\alpha_k, \beta_k)}. \]

A similar formula holds for finding the LCM of several integers, by taking the largest exponent for each prime.

What is the smallest positive integer \(n\) such that \(\mbox{lcm}(n, 30) = 180?\)

---

The prime factorization of \(30\) is \(30 = 2 \times 3\times 5 \) and the prime factorization of \(180\) is \(180=2^2\times 3^2\times 5\). Then \(n\) must include a factor of \(2^2\) and a factor of \(3^2\), so the smallest positive integer \(n\) is \(n=2^2 \times 3^2 = 4 \times 9 = 36\). \(_\square\)

Recall that the greatest common divisor of a set of integers is the largest (positive) number which is a divisor of each integer in the set. The two concepts are intimately related; in particular, they satisfy the following theorem:

\[ \gcd(a,b) \times \mbox{lcm}(a,b) = ab \]

This is straightforward from the descriptions using prime factorizations, but it can also be proved directly. Consider the integer \(m = \frac{ab}{\gcd(a,b)};\) since it equals \(\frac{a}{\gcd(a,b)} b,\) and the first fraction is an integer, it is a multiple of \(b;\) similarly, it is a multiple of \(a\) since it can be rewritten as \(a \frac{b}{\gcd(a,b)}.\) So \(m\) is a common multiple of \(a,b.\) This shows that \(\text{lcm}(a,b) \le m,\) and multiplying through by the denominator of \(m\) gives \(\gcd(a,b) \times \text{lcm}(a,b) \le ab.\)

But a similar "dual" argument shows the reverse inequality: let \(d = \frac{ab}{\text{lcm}(a,b)}.\) Then \(d \left( \frac{\text{lcm}(a,b)}a \right) = b,\) and the quantity in parentheses is an integer, so \(d|b.\) Similarly \(d|a.\) So \( d\le \gcd(a,b),\) and multiplying through by the denominator of \(d\) gives \( ab \le \gcd(a,b) \times \text{lcm}(a,b).\)

These two statements together show that the two sides are equal. \(_\square\)

Given that \(a\) and \(b\) are 2 integers such that \( 13 \gcd(a,b) = \mbox{lcm}(a,b) \) and \( a + b = 2016\), what are the values of \(a\) and \(b?\)

---

Let \( G = \gcd(a,b)\) and \( L = \mbox{lcm}(a,b)\). Let \( a = a^* G\) and \( b = b^* G,\) where \( \gcd(a^*, b^*) = 1 \) by construction. Since \( (a^*G)\times (b^*G) = ab = GL = G \times 13 G ,\) we get that \( a^* b^* = 13. \) Hence, we have \( \{ a^*, b^* \} = \{ 1, 13\} .\) Without loss of generality, we may assume that \(a\leq b,\) and thus \( a = G, b = 13 G \).

Since \( 2016 = a + b = G + 13G = 14 G, \) \(G = \frac{2016} { 14} = 144 \). Thus, \( \{a, b\} = \{ 144, 1872 \} \). \(_\square\)

This relationship with the gcd also gives an efficient algorithm for computing the LCM that does not require prime factorization. Since the Euclidean algorithm computes \( \gcd(a,b)\) quickly, the value of \( \text{lcm}(a,b)\) can be recovered as \( \frac{ab}{\gcd(a,b)}.\)

The properties of the LCM are dual to those of the GCD, and many of them can be deduced from the explicit relationship between the two proved above.

• The LCM of a list of numbers divides any other common multiple.

This is clear from the formula via prime factorization; it can also be deduced from the analogous property of the GCD.

• The intersection of the sets of multiples of the individual numbers in a list equals the set of multiples of their LCM.

This is essentially a statement about ideals in the ring of integers.

• The LCM of a list of numbers can be computed two at a time, e.g. \( \text{lcm}(a,b,c) = \text{lcm}\big(\text{lcm}(a,b),c\big).\)

So algorithms that compute the LCM can concentrate on the LCM of a pair of numbers since the LCM of a larger list can be computed from LCMs of pairs.