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 one first writes the fractions with a common denominator, which is the LCM of and
Since this sum can be rewritten as
Find the lcm of and
Here is a list of the positive multiples of each number:
The first number that appears on both lists is
The LCM is important in many applications of elementary number theory, including the Chinese remainder theorem, where appears as the modulus of the unique solution to a system of equations modulo and
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 using prime factorizations.
The LCM can be read off from these factorizations by taking the maximum exponent for each prime:
Generalizing this example, if the prime factorizations of and are
where the are distinct primes and the and are nonnegative integers, then
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 such that
The prime factorization of is and the prime factorization of is . Then must include a factor of and a factor of , so the smallest positive integer is .
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:
This is straightforward from the descriptions using prime factorizations, but it can also be proved directly. Consider the integer since it equals and the first fraction is an integer, it is a multiple of similarly, it is a multiple of since it can be rewritten as So is a common multiple of This shows that and multiplying through by the denominator of gives
But a similar "dual" argument shows the reverse inequality: let Then and the quantity in parentheses is an integer, so Similarly So and multiplying through by the denominator of gives
These two statements together show that the two sides are equal.
Given that and are 2 integers such that and , what are the values of and
Let and . Let and where by construction. Since we get that Hence, we have Without loss of generality, we may assume that and thus .
Since . Thus, .
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 quickly, the value of can be recovered as
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.
- The LCM of a list of numbers can be computed two at a time, e.g.
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.
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?
Cicadas live underground for most of their lives and only emerge in the spring of their last year in order to mate and reproduce. The North American Genus of Cicada, known as Magicicada, has an extremely long life cycle of 13 or 17 years. Each brood of cicadas has its own emergent years and life cycles.
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