Greatest Common Factor and Least Common Multiple
GCF and LCM
How are factors involved in the following scenario?
Gary has 20 table tennis balls and 16 paddles. He wants to sell common sized packages containing both paddles and balls. What is the greatest number of packages he can sell with no left over balls or paddles?
We use factors to search for solutions to the first problem.
|
1 · 20 = 20 and 1 · 16 = 16 |
One package with 20 balls and 16 paddles. |
|
2 · 10 = 20 and 2 · 8 = 16 |
Two packages each with 10 balls and 8 paddles. |
|
4 · 5 = 20 and 4 · 4 = 16 |
Four packages each with 5 balls and 4 paddles. |
The question can be answered by finding the greatest common factor. If Gary wants to divide the balls and paddles into packages with each package containing the same number of balls then we are looking for a number that is a factor of both. This is what we would call a common factor. The above illustration shows that Gary has three options for packaging the balls and paddles with one, two, or four packages. If we want to create as many packages as possible then we are looking for the greatest common factor.
Example:
Set of factors of 20 is {1, 2, 4 , 5, 10, 20}
Set of factors of 16 is {1, 2, 4 , 8, 16}
From these two lists we see that the greatest common factor of 20 and 16 is 4, so Gary would be able to sell four packages each containing four paddles and five balls.
This problem motivates a need for being able to determine the greatest common factor for two or more values.
Definition of Greatest Common Factor (GCF) :
The greatest common factor (GCF) of two natural numbers n and m is the greatest natural number k that is a factor of both n and m. We symbolize this as GCF(n, m) = k.
Example:
Relating this definition to the problem we solved on the previous page, we see that the two numbers n and m are the numbers 20 and 16. We may write the solution symbolically as GCF(20, 16) = 4. This says "the greatest common factor of 20 and 16 is 4."
The number k in the definition corresponds to the 4 in the problem. It is the factor of the greatest value shared by both n and m. The number k is the Greatest Common Factor of 20 and 16.
One method for finding the greatest common factor is to choose the value that is the greatest value in the intersection of the sets of common factors.
Example: Find the GCF(20, 16).
The set of factors of 20 is {1, 2, 4, 5, 10, 20} and the set of factors of 16 is {1, 2, 4, 8, 16}.
{1, 2, 4, 5, 10, 20} ∩ {1, 2, 4, 8, 16} = {1, 2, 4} which has greatest value 4.
So, GCF(20, 16) = 4.
Notice that an intermediate step in this method applied to the problem at the beginning of the session gives all possibilities for packaging all the balls and paddles: one, two, or four packages.
Example: Find GCF(18, 24).
The set of factors of 18 is {1, 2, 3, 6, 9, 18}
and set of factors of 24 is {1, 2, 3, 4, 6, 8, 12, 24}.
{1, 2, 3, 6, 9, 18} ∩ {1, 2, 3, 4, 6, 8, 12, 24} = {1, 2, 3, 6} which has greatest value 6.
The GCF (18, 24) = 6.
As the number of factors becomes larger, it is not practical to list every factor and search for the greatest. Instead, we can use what we know about prime factorization to help us find the greatest common factor.
Example: Find GCF (308, 1176).
First, we find the prime factorizations of the numbers.
308 = 22 · 7 · 11 and 1176 = 23 · 3 · 72
Next, we examine how the factors correspond. For now, we will expand the exponent notation and line up the factors that match, leaving any other factors at the end of the factorization.
We see that 2 · 2 · 7 are the factors that are in both factorizations.
Therefore the GCF (308, 1176) = 2 · 2 · 7 = 28.
Further, notice that when the factors are matched up, there are three factors of 2 in 1176 but there are only two factors of 2 in 308. We were only able to match up the lesser number of 2's. This corresponds to the least exponent of the factor 2.
So to get the GCF of two numbers, we only need to take the common prime factors from the prime factorizations and compare their exponents. In each case, we take the exponential expression that has the least exponent and multiply those together.
Example: We reconsider the previous example to illustrate the use of the exponents.
Find GCF (308, 1176).
First, we find the prime factorizations of the numbers.
308 = 22 · 7 · 11
1176 = 23 · 3 · 72
For the common prime factors, the least exponent for 2 is 2 and the least exponent for 7 is 1. So, in this case we have GCF (308, 1176) = 22 · 71 = 4 · 7 = 28.
Example: Find GCF(4950, 7020)
4950 = 2 · 32 · 52 · 11
7020 = 22 · 33 · 5 · 13
The common prime factors are 2, 3, and 5. The least exponent for 2 and 5 is one (21 = 2 and 51 = 5) and for 3 is two.
So the GCF (4950, 7020) = 2 · 32 · 5 = 90.
Example: Find GCF(7920, 92664)
7920 = 24 · 32 · 5 · 11
92664 = 23 · 34 · 11 · 13
The common prime factors are 2, 3, and 11. The least exponent for 2 is 3 (23), for 3 is 2 (32), and for 11 is 1 (111).
So the GCF (7920, 92664) = 23 · 32 · 11 = 792.
How are multiples involved in the following scenario?
A machine contains two gears. One gear has 12 teeth and the other has 20 teeth. The gears are aligned by a mark drawn from the center of the first gear to the center of the second gear. What is the smallest number of revolutions of the first gear necessary to realign the mark?
We begin by listing, for each gear, the number of teeth that would pass the starting mark after the first revolution, second revolution, third revolution, … .
First gear: 12, 24, 36, 48, 60 , 72, 84, 96, 108, 120 , 132, 144, 156, 168, 180 , 192, …
Second gear: 20, 40, 60 , 80, 100, 120 , 140, 160, 180 , 200, 220, 240 , 260, 280, 300 ,…
Notice that we are listing the multiples of 12 and 20. The first gear will be aligned with the second gear after five revolutions. (Also, note the second gear will have made three revolutions.)
This question was answered using the least common multiple. Notice that the mark on the first gear returns to its original position after each full revolution. This will happen when it has gone through 12 teeth, 24 teeth, 36 teeth, etc. The mark on the second gear returns to its original position after it has made any number of full revolutions. This will happen when it has gone through 20 teeth, 40 teeth, 60 teeth, 80 teeth, etc.
Notice that 12, 24, 36, … are multiples of 12 and 20, 40, 60, … are multiples of 20.
The mark will be realigned only when a value that is both a multiple 12 and of 20 is reached. The mark will be realigned for the first time when the first such multiple is reached. Therefore, we are looking for the Least Common Multiple of 12 and 20.
Definition of Least Common Multiple (LCM) :
The least common multiple (LCM) of two natural numbers n and m is the smallest valued number h so that h is a multiple of both n and m. We symbolize this as LCM(n, m) = h.
Example:
Relating this definition to the problem we solved on the previous page, we see that the two numbers n and m are the numbers 12 and 20. We may write the solution symbolically as LCM(12, 20) = 60. This says "the least common multiple of 12 and 20 is 60."
The number h in the definition corresponds to the 60 in the problem. It has the least value if the multiples shared by both n and m. The number h is the Least Common Multiple of 12 and 20.
One method for finding the least common multiple is to choose the value that is the minimum value in the intersection of the sets of multiples.
Example: Find the LCM(12, 20).
We find the set of their natural number multiples and then find the least value in the intersection of the two sets.
Set of multiples of 12 is A = {12, 24, 36, 48, 60, 72, 84, 96, 108, 120, …}
Set of multiples of 20 is B = {20, 40, 60, 80, 100, 120, 140, 160, 180, …}
A ∩ B = {60, 120, 180, …} which has the least value 60.
The LCM(12, 20) = 60.
Notice that the intermediate step in the problem gives all the common multiples.
Since we have found the least common multiple, 60, for the gear problem, we can now answer the question to the gear problem. The question asked how many revolutions are needed to realign the mark. Since we know the first gear must pass 60 teeth and after every 12 it has made one revolution, we know it must make 5 revolutions before the marks are aligned for the first time (60 ÷ 12 = 5). (Also, note that the second gear must make three revolutions for 60 teeth to pass the mark, 60 ÷ 20 = 3.)
As with the GCF, finding the LCM of larger numbers by listing multiples is not very practical. Also, just like the GCF, we can use prime factorization to help.
Example: Find LCM(308,1176).
Again we list the prime factors of the values.
308 = 22 · 7 · 11
1176 = 23 · 3 · 72
Since we are looking for multiples, every multiple of 308 must contain 22 · 7 · 11 as factors and every multiple of 1176 must contain 23 · 3 · 72 as factors. This means that 2, 3, 7, and 11 must be prime factors in any common multiple. For 2 and 7, which appear in both lists, we need the highest power of that prime as a factor to create the LCM, since 23 is automatically a multiple of 22. So using the highest power of each prime, LCM (308,1176) = 23 · 3 · 72 · 11 = 12,936.
Entities should not be multiplied unnecessarily.
—William of Occam (1300-1439)