29 Least Common Multiple and other Topics
[LA math standards will be here.]
Least Common Multiple
There are a finite number of factors for any given number. On the other hand, there are an infinite number of nonzero multiples of a number. For instance the list of multiples of [latex]2[/latex] are all of the even numbers. It’s impossible to list all of them, because this is an infinite set. A multiple of a number [latex]c[/latex] is [latex]nc[/latex]where [latex]n[/latex] is a whole number. In other words, to find a multiple of [latex]c[/latex], multiply [latex]c[/latex] by a whole number. Although [latex]0[/latex] is a multiple of every number, we usually omit listing it as a multiple. The (nonzero) multiples of [latex]6[/latex] are listed here:
[latex]6, 12, 18, 24, 30, 36, 42, ...[/latex]
To list the multiples of a number, you begin with the number itself, then the number times [latex]2[/latex], then the number times [latex]3[/latex], etc. Since multiplication is repeated addition, you could repeatedly add the number to get the next multiple.
Exercise 1
a. List the first 10 multiples of 8.
Solution
b. List the first 10 multiples of 12.
Solution
c. Of the list you produced in parts a and b, list the multiples that 8 and 12 have in common.
Solution
d. From part c, what is the smallest multiple that 8 and 12 have in common?
Solution
e. Is there a greatest common multiple that 8 and 12 have in common? Is so, what is it? Before you answer, remember that in a and b, you only listed the first 10 multiples of 8 and 12.
Solution
Just like with the greatest common factor (GCF), many people don’t really think about what LEAST COMMON MULTIPLE means. Every number has an infinite number of multiples. Every set of numbers has an infinite number of multiples in common. The LEAST COMMON MULTIPLE is the smallest multiple they have in common.
Definition – Least Common Multiple
In exercise 1, we write [latex]LCM(8, 12) = 24[/latex]. The order of the numbers in the parentheses is irrelevant. So, [latex]LCM(8, 12) = LCM(12, 8)[/latex]. It is NOT an ordered pair. Also, you can find the least common multiple of a large set of numbers. Theoretically, we can find the least common multiple of several numbers, such as [latex]LCM(2, 3, 4, 5, 6, 7, 8, 9, 10)[/latex], by listing several (or more) multiples of each of these numbers until we find the smallest one all of them have in common. However, usually this is not the efficient way to find the LCM, so we will be exploring another way to find it using prime factorization.
The problem with trying to find the least common multiple this way is that you may have to write a lengthy list of multiples of each number until you finally find a multiple they all have in common. For instance, if you were asked to find the LCM(59,61), you wouldn’t find a multiple they each have in common until you wrote 61 multiples of 59 and 59 multiples of 61. That is because these are prime numbers, so the least common multiple is their product: [latex]59 \cdot 61[/latex]. This is the case with any numbers that are relatively prime as well. (Remember 4 and 15 are relatively prime, although neither is prime.)
Several special cases of [latex]GCF[/latex] and [latex]LCM[/latex]:
i. If [latex]x[/latex]and [latex]y[/latex] have no factors in common, that is, [latex]GCF(x,y) = 1[/latex], then [latex]LCM(x,y) = xy[/latex].
ii. If [latex]LCM(x,y) = xy[/latex], then [latex]x[/latex] and[latex]y[/latex] have no factors in common, that is, [latex]GCF(x,y) = 1.[/latex]
A more efficient way to find the least common multiple of a set of numbers is to find the prime factorization of each number, and then BUILD the least common multiple. We will explore this using the prime number squares in your Material Cards.
Below is the prime factorization of three numbers, A, B and C represented by prime number squares. Below each of them, we write the number in prime factorization form.
 [latex]A = 2 \cdot 3^{2} \cdot 5 \cdot 7[/latex] |
 [latex]B = 2^{3} \cdot 5 \cdot 7^{2} \cdot 11[/latex] |
 [latex]C = 2^{2} \cdot 3^{2} \cdot 5 \cdot 7 \cdot 11 \cdot 13[/latex] |
Now, we are going to use the prime factorization to build the LEAST COMMON MULTIPLE of a set of numbers. The least common multiple is a multiple that the numbers have in common, but that has the least number of prime factors possible. To build a multiple of a number, we can add one or more prime squares as we want. But differently, to build a least common multiple, we only add in a prime factor if it is necessary.
Let’s say we want to build the least common multiple of A, B and C. In order to be a multiple of A, we need to have all the prime factors of A. So, we start building the multiple by putting in the factors of A:
All the prime factors of B must also be in the multiple. B has three factors of 2, but there is only one 2 in the multiple so far. So, the common multiple will need two more factors of 2. Similarly, B has two prime factors of 7, but there is only one 7 in the multiple so far. So, the common multiple will need one more factor of 7. B has one factor of 5, which is already there. B also has one factor of 11. That is not there, so must be put in. Therefore, two factors of 2, one factor of 7 and a factor of 11 must be joined with the other prime factors in the common multiple. Once this is done, we have built the least common multiple of A and B:
The prime factorizations of A, B and C are shown below for your convenience.
We have built the least common multiple of A and B. To find the least common multiple of A, B and C, we need to make sure all the prime factors of C are also in the multiple. C has two factors of 2, which are already in the multiple, two factors of 3, which are already in the multiple, one factor each of 5, 7 and 11, each of which is already in the multiple, and a factor of 13, which is not in the multiple. So 13 is the only prime factor that needs to be joined with the factors already in the multiple we are building.
The above is a multiple of A, B and C. We not only built a multiple; we actually built the LEAST COMMON MULTIPLE of A, B and C. Note it is a multiple of A, B and C; therefore it is a common multiple. It is the least common multiple because if any of the factors were removed, it wouldn’t be a multiple of one of the numbers. For instance, if a factor of 2 was removed, it would not be a multiple of A. If a factor of 3 was removed, it would not be a multiple of A or C. If a factor of 7 was removed, it would not be a multiple of B, etc. If a factor of 11 was removed, it would not be a multiple of B or C. If a factor of 13 was removed, it would not be a multiple of C.
We write:
[latex]LCM(A, B, C) = 2^{3} \cdot 3^{2} \cdot 5 \cdot 7^{2} \cdot 11 \cdot 13[/latex].
In the exercise below, let’s practice more how to build the least common multiple of numbers with given prime factorization.
Build the least common multiple of given numbers using prime number squares. Then, write the prime factorization of the least common multiple.
a. [latex]A = 2^{2} \cdot 3^{5} \cdot 5 \cdot 13[/latex] and [latex]B = 2^{2} \cdot 3^{2} \cdot 7^{3} \cdot 11^{2} \cdot 13[/latex].
Then [latex]LCM(A, B) =\underline{\qquad\qquad\qquad\qquad}[/latex]
b. [latex]A = 2^{2} \cdot 11 \cdot 19[/latex] and [latex]B = 2 \cdot 3^{2} \cdot 7 \cdot 11^{2}[/latex] and [latex]C = 2^{2} \cdot 3^{4} \cdot 7^{3} \cdot 13^{2} \cdot 19[/latex].
Then [latex]LCM(A, B, C) =\underline{\qquad\qquad\qquad\qquad}[/latex]
c. [latex]A = 2 \cdot 5^{3} \cdot 11 \cdot 19[/latex] and [latex]B = 2^{4} \cdot 3^{6} \cdot 5^{2} \cdot 23^{2}[/latex] and [latex]C = 5^{4} \cdots7^{6} \cdot 11^{2} \cdot 23[/latex]
Then [latex]LCM(A, B, C) =\underline{\qquad\qquad\qquad\qquad}[/latex]
Look back at the part c. in Exercise 2.
[latex]A = 2 \cdot 5^{3} \cdot 11 \cdot 19[/latex] and [latex]B = 2^{4} \cdot 3^{6} \cdot 5^{2} \cdot 23^{2}[/latex] and [latex]C = 5^{4} \cdots7^{6} \cdot 11^{2} \cdot 23[/latex]
The answer is [latex]LCM(A, B, C) = 2 \cdot 3^{6} \cdot 5^{4} \cdot 7^{6} \cdot 11^{2} \cdot 19 \cdot 23^{2}[/latex]
If the numbers are prime factored using exponents, then the least common multiple contains each of the prime factors shown in any of the numbers, and the exponent on each of the prime numbers is the highest exponent found on that prime number factor in the prime factorization of the numbers.
For instance, the prime numbers in the prime factorization of A, B and C are 2, 3, 5, 7, 11, 19 and 23. So begin by writing the product of these prime numbers: [latex]2 \cdot 3 \cdot 5 \cdot 7 \cdot 11 \cdot 19 \cdot 23[/latex]
2 is a factor in A and B. The highest power of 2 found in either prime factorization of A and B is 1. 3 is a factor found in B, as [latex]3^{6}[/latex]. So, the highest power of 3 is 6. 5 is a factor of all three numbers. In A, the exponent on 5 is 3; in B, the exponent on 5 is 2; in C, the exponent on 5 is 4. So, the highest power of 5 is 4. Similarly, do the same for all of the other prime factors. Write the highest exponent on the factor.
Therefore, [latex]LCM(A, B, C) = 2 \cdot 3^{6} \cdot 5^{4} \cdot 7^{6} \cdot 11^{2} \cdot 19 \cdot 23^{2}[/latex]
Find the greatest common factor and least common multiple for each set of numbers, written in prime factorization. Assume a, b, c, d, and e are different prime numbers.
a. Let [latex]A = 2^{2} \cdot 3^{5} \cdot 5 \cdot 13[/latex] and [latex]B = 2^{2} \cdot 3^{2} \cdot 7^{3} \cdot 11^{2} \cdot 13[/latex]
[latex]GCF(A, B)=\underline{\qquad\qquad\qquad\qquad}[/latex]
[latex]LCM(A, B)=\underline{\qquad\qquad\qquad\qquad}[/latex]
b. Let [latex]A = 2^{2} \cdot 11 \cdot 19[/latex] and [latex]B = 2 \cdot 3^{2} \cdot 7 \cdot 11^{2}[/latex] and [latex]C = 2^{2} \cdot 3^{4} \cdot 7^{3} \cdot 13^{2} \cdot 19[/latex]
[latex]GCF(A, B)=\underline{\qquad\qquad\qquad\qquad}[/latex]
[latex]LCM(A, B)=\underline{\qquad\qquad\qquad\qquad}[/latex]
c. Let [latex]X = a^{5} \cdot b^{4} \cdot c^{5} \cdot d[/latex] and [latex]Y = b^{2} \cdot c^{3} \cdot d^{2} \cdot e^{2}[/latex] and [latex]Z = a^{2} \cdot c^{4} \cdot d^{3} \cdot e^{2}[/latex]
[latex]GCF(X, Y, Z)=\underline{\qquad\qquad\qquad\qquad}[/latex]
[latex]LCM(X, Y, Z)=\underline{\qquad\qquad\qquad\qquad}[/latex]
d. Let [latex]X = a^{6} \cdot b^{3} \cdot c \cdot d[/latex] and [latex]Y = b^{4} \cdot c^{4} \cdot d^{3} \cdot e^{7}[/latex] and [latex]Z = a^{2} \cdot c^{4} \cdot d^{2} \cdot e^{3}[/latex]
[latex]GCF(X, Y, Z)=\underline{\qquad\qquad\qquad\qquad}[/latex]
[latex]LCM(X, Y, Z)=\underline{\qquad\qquad\qquad\qquad}[/latex]
So far, the prime factorization of numbers has been given, and all you had to do was to build the prime factorization of the least common multiple. Now, your job will be to first prime factor numbers; then you can build the least common multiple from the prime factorizations. In the end, the least common multiple is a number. Multiply the factors in the least common multiple to find the one number that is the least common multiple.
Find the least common multiple of 15, 18 and 20
Solution
Prime factor each of these numbers. [latex]15 = 3 \cdot 5, 18 = 2 \cdot 3 \cdot 3[/latex], and [latex]20 = 2 \cdot 2 \cdot 5[/latex]
Build the least common multiple by first “throwing in” the prime factors that make up the prime factorization of 15; then “throw in” any prime factors needed for 18; next, “throw in” any prime factors needed for 20. We get [latex]LCM(15, 18, 20) =3 \cdot 5 \cdot 2 \cdot 3 \cdot 2 = 2^{2} \cdot 3^{2} \cdot 5= 180[/latex]
Exercise 4 below provides more practice for us.
Find the least common multiples. Show the prime factorization of each number, and how you use it to build the least common multiple.
a. [latex]LCM (6, 8, 10)[/latex]
Solution
b.[latex]LCM (25, 35, 40)[/latex]
Solution
c. [latex]LCM (49, 91, 26)[/latex]
Solution
d. [latex]LCM(56, 24, 30)[/latex]
Solution
e. [latex]LCM(22, 34, 55)[/latex]
Solution
Note how easy it is to find the least common multiple of a larger set of numbers using prime factorization. We’ll find: LCM(2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14)
We don’t need to expressly write down the prime factorization of the 12 numbers because it’s easy enough to do that in our head. For instance, the prime factorization of 4 is [latex]2 \cdot 2[/latex], the prime factorization of 10 is [latex]2 \cdot 5[/latex], and the prime factorization of 13 is 13.
We build up the LCM of 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13 and 14 by first making sure the prime factorization of 2 is there.
Step 1: Make sure the prime factorization 2 is there. So far, LCM: 2
Step 2: Make sure the prime factorization 3 is there. We need to “throw in” a 3 to the LCM. So far, LCM: [latex]2 \cdot 3[/latex]
Step 3: Make sure the prime factorization 4 is there. We need to “throw in” a 2 to the LCM. So far, LCM: [latex]2 \cdot 3 \cdot 2[/latex]
Step 4: Make sure the prime factorization 5 is there. We need to “throw in” a 5 to the LCM. So far, LCM: [latex]2 \cdot 3 \cdot 2 \cdot 5[/latex]
Step 5: Make sure the prime factorization 6 is there. We don’t need to “throw in” any factor(s) to the LCM, so there is no change to the LCM. So far, LCM: [latex]2 \cdot 3 \cdot 2 \cdot 5[/latex].
Step 6: Make sure the prime factorization 7 is there. We need to “throw in” a 7 to the LCM. So far, LCM: [latex]2 \cdot 3 \cdot 2 \cdot 5 \cdot 7[/latex]
Step 7: Make sure the prime factorization 8 is there. We need to “throw in” a 2 to the LCM. So far, LCM: [latex]2 \cdot 3 \cdot 2 \cdot 5 \cdot 7 \cdot 2[/latex]
Step 8: Make sure the prime factorization 9 is there. We need to “throw in” a 3 to the LCM. So far, LCM: [latex]2 \cdot 3 \cdot 2 \cdot 5 \cdot 7 \cdot 2 \cdot 3[/latex]
Step 9: Make sure the prime factorization 10 is there. We don’t need to “throw in” any factor(s) to the LCM, so there is no change to the LCM. So far, LCM: [latex]2 \cdot 3 \cdot 2 \cdot 5 \cdot 7 \cdot 2 \cdot 3[/latex]
Step 10: Make sure the prime factorization 11 is there. We need to “throw in” an 11 to the LCM. So far, LCM: [latex]2 \cdot 3 \cdot 2 \cdot 5 \cdot 7 \cdot 2 \cdot 3 \cdot 11[/latex]
Step 11: Make sure the prime factorization 12 is there. We don’t need to “throw in” any factor(s) to the LCM, so there is no change to the LCM. So far, LCM: [latex]2 \cdot 3 \cdot 2 \cdot 5 \cdot 7 \cdot 2 \cdot 3 \cdot 11[/latex]
Step 12: Make sure the prime factorization 13 is there. We need to “throw in” a 13 to the LCM. So far, LCM: [latex]2 \cdot 3 \cdot 2 \cdot 5 \cdot 7 \cdot 2 \cdot 3 \cdot 11 \cdot 13[/latex]
Step 13: Make sure the prime factorization 14 is there. We don’t need to “throw in” any factor(s) to the LCM, so there is no change to the LCM. So far, LCM: [latex]2 \cdot 3 \cdot 2 \cdot 5 \cdot 7 \cdot 2 \cdot 3 \cdot 11 \cdot 13[/latex]
That’s it! You have now built up the LEAST common multiple of all 12 numbers! You can check to make sure that the prime factorization of each of the 12 numbers is indeed in the prime factorization of the least common multiple you built. Furthermore, if any of the prime factors were removed, it wouldn’t be a multiple of all 12 numbers. Therefore, the prime factorization of the LCM is as shown below:
[latex]LCM(2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14) = 2 \cdot 3 \cdot 2 \cdot 5 \cdot 7 \cdot 2 \cdot 3 \cdot 11 \cdot 13[/latex].
If these factors are multiplied together,
[latex]LCM(2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14) = 360, 360[/latex].
The prime factorization of the LCM may have been written with the factors in ascending order using exponents:
[latex]2^{3} \cdot 3^{2} \cdot 5 \cdot 7 \cdot 11 \cdot 13[/latex].
Use prime factorization to build the least common multiple. Show the prime factorization as the number is built. Then, multiply the factors to find the answer.
a. LCM(3, 4, 6, 7, 9, 10, 12, 14, 15, 18, 20)
Solution
b. LCM(2, 3, 9, 11, 14, 15, 16, 17, 18, 22)
Solution
c. LCM(5, 6, 7, 8, 12, 14, 15, 17, 18, 25)
Solution
d. LCM(15, 18, 20, 25, 30, 35, 42, 45)
Solution
The Relation between GCF and LCM
Let’s say you know the greatest common factor of 165 and some other number was 3, and the least common multiple of the same two numbers was 15,015. How would you figure out what the other number was?
First, it’s a good idea to write down what you know. Let N be the other number.
Then, GCF(165, N) = 3 and LCM (165, N) = 15,015.
Since 3 is a factor, and in fact the greatest common factor, of both 165 and N, then each number can be written as 3 times something, and the other factor you obtain for 165 should be relatively prime to the other factor you obtain for N, since 3 is the greatest common factor of 165 and N.
So, let’s rewrite, LCM (165,N) = 15,015 like this: LCM ([latex]3 \times 55[/latex], [latex]3 \times \underline{\qquad}[/latex]) = 15,015
In other words, I know N = 3 [latex]\times\underline{\qquad}[/latex], but I have to figure out what goes in the blank to figure out what N is. If you want to introduce another variable, like M, instead of writing a blank, that works just as well. It’s up to you.
To find the LCM of [latex]3 \times 55[/latex] and 3 [latex]\times \underline{\qquad}[/latex], where the 55 and the number on the blank have no common factors, you would multiply [latex]3 \times 55 \times\underline{\qquad}[/latex]. But we know the product should be 15,015. So, the number that must go on the blank must be 91, since [latex]3 \times 55 times 91 = 15,015[/latex]. So, now we can figure out what N is: [latex]N = 3 \times 91 = 273[/latex].
Let’s see if this makes sense by first rewriting 165 and 273 either in prime factored form or as the GCF(165,273) times something; then we’ll figure out the GCF and LCM from the factored form, and see if it agrees with our original problem.
[latex]165 = 3 \times 55[/latex] and 273 = [latex]3 \times 91[/latex]. First, make sure 3 is really a factor of each number!
Now, convince yourself that 3 really is the greatest common factor of 165 and 273 by checking to see that the other factor of one number is relatively prime (no factors in common) with the other factor of the other number. So, ask yourself if 55 and 91 have any factors in common (besides 1) if you aren’t sure, then prime factor each of these numbers first ([latex]55 = 5 \times 11[/latex] and [latex]91 = 7 \times 13[/latex]); note that they have no factors in common.
Since 3 is the greatest common factor, then the least common multiple is obtained by multiplying [latex]3 times 55 times 91[/latex], which is 15,015 which is what it should be according to the original information given. Therefore, 273 really was the number we were looking for.
N = 273
There is another way to do the above problem using the following property:
For any two numbers, m and n, the following is always true:
[latex]m \times n = GCF(m, n) \times LCM (m, n)[/latex].
Key Takeaways – Property of GCF and LCM
For any two numbers, m and n, the following is always true:
[latex]m \times n = GCF(m, n) \times LCM (m, n)[/latex].
The example asks us to verify this property for the given numbers.
Verify the above property for numbers 15 and 18.
Solution:
Since GCF(15, 18) = 3 and LCM(15, 18) = 90, we want to verify that the product of the two numbers, 15 and 18, equals the product of the GCF and LCM of the two numbers.
[latex]15 \cdot 18 = 270[/latex]; GCF(15, 18) [latex]\cdot[/latex] LCM(15, 18) = [latex]3 \cdot 90 = 270[/latex]
Therefore, [latex]15 \cdot 18 =[/latex] GCF(15, 18) [latex]\cdot[/latex] LCM(15, 18).
Note: This equation is not true for more than two numbers [latex]r \times s \times t \neq GCF(r, s, t) \times LCM(r, s, t)[/latex]. There is a counterexample in the example below.
Show that the above property does not work for three numbers.
Solution:
We use the numbers 4, 6 and 8 as a counterexample.
GCF(4, 6, 8) = 2 and LCM(4, 6, 8) = 24
[latex]4 \cdot 6 \cdot 8 = 192[/latex]; GCF(4, 6, 8) [latex]\cdot[/latex] LCM(4, 6, 8) = [latex]2 \cdot 24 = 48[/latex]
Clearly, [latex]4 \cdot 6 \cdot 8 \neq[/latex] GCF(4, 6, 8) [latex]\cdot[/latex] LCM(4, 6, 8)
The property can be used to find the LCM of two numbers if you know the GCF. For instance, if you were asked to find the GCF and LCM of 24 and 30. You can easily find the GCF, which is 6. To find the LCM, multiply the two numbers together, and divide by the GCF. (This should make sense to you intuitively if you think about it: You wouldn’t list the GCF twice as you build the LCM. Also, the GCF will cancel into either of the two numbers since it is a factor of each.)
So,
[latex]LCM(24, 30) = (24 \cdot 30) \div 6 = 120[/latex].
If GCF(1176, 288) = 24, find the LCM(1176, 288).
Solution
When we are given one number and the GCF and LCM of it with another unknown number, we can also use the property to find the unknown number, as shown in the example below.
Find [latex]N[/latex] if [latex]GCF(165, N) = 3[/latex] and [latex]LCM (165, N) = 15,015[/latex].
Solution:
In this case, the two numbers are [latex]165[/latex] and [latex]N[/latex], the [latex]GCF[/latex] of them is [latex]3[/latex] and the [latex]LCM[/latex]is [latex]15,015[/latex].
Plug these values into the equation shown above in the property:
[latex]165N=3 \times 15,015[/latex].
Divide both sides by 165 to find N:
[latex]N= \frac{3 \times 15015}{165} =273[/latex].
a. Find X if GCF(2940, X) = 105 and LCM(2940, X) = 79,380
Solution
b. If the greatest common factor of 3,211 and another number is 247 and the least common multiple of the same two numbers is 48,165, then what is the other number?
Solution
If you aren’t given at least one of the numbers, there might be more that one possible solution.
Exercise 8
Figure out the possibilities for a and b if all you know is GCF(a, b) = 2 and LCM(a, b) = 20.
Solution
The next few problems are a review of GCF and LCM. You now have several methods you can use to find the GCF and LCM. The exercise below provides you more problems to practice.
Exercise 9