# 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,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}.\)

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.\)Find the lcm of \( 30,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.\)

## Computing the lcm

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.

\[ \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.\)

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?\)

Solution:The prime factorization of \(30\) is \(30 = 2 *3* 5 \) and the prime factorization of \(180\) is \(180=2^2*3^2*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\)

## Connection with the gcd

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 = ab/\gcd(a,b)\); since it equals \(\dfrac{a}{\gcd(a,b)} b,\) and the first fraction is an integer, it is a multiple of \(b,\) and similarly it is a multiple of \(a\) since it can be rewritten as \(a \dfrac{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) \text{lcm}(a,b) \le ab.\)

But a similar "dual" argument shows the reverse inequality: let \(d = ab/\text{lcm}(a,b).\) Then \(d \left( \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) \text{lcm}(a,b).\)

These two statements together show that the two sides are equal.

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\)?

Solution: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, \) thus \(G = \frac{2016} { 14} = 144 \). Thus, \( \{a, b\} = \{ 144, 1872 \} \).

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 \( ab/\gcd(a,b).\)

## Properties of the lcm

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}(\text{lcm}(a,b),c).\)

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.

## Problem Solving

For the end of year examinations, Stella wants to bring a bag of candies to share with every student who earns an "A" in her class.

She knows that if there are 2, 3, 4, 5, 6, or even 7 top students, then she should be able to distribute the candies out evenly, and she doesn't want to take any candies home with her.

Given that she is going to bring at least 10 candies, what is the minimum number that she must bring?

The state of Kansas only gets 2 broods of Magicicada. The first brood last appeared in 1998, and has a life cycle of 17 years. The second brood last appeared in 2011, and has a life cycle of 13 years. (It is now 2014.) How many years will it take for both broods to emerge together?

###### Image credit: Instagram user brandycandy, Data: Magicicada.org

**Cite as:**Lowest Common Multiple.

*Brilliant.org*. Retrieved from https://brilliant.org/wiki/lowest-common-multiple/