Greatest common factor by listing
A food bank has 18 tins and 24 packets to share out into identical parcels, with nothing left over. How many parcels can it make, at most?
Where you are 4 in Greatest common factor and least common multiple
When you reach for it
On Saturday morning the food bank has 18 tins of beans and 24 packets of pasta to give out. Tamsin, who runs the packing table, wants every parcel to be exactly like every other, and she wants nothing left on the table at the end. How many parcels can she make?
Start with the tins. If she makes some number of parcels, the 18 tins are shared equally among them, so that number must go into 18 with nothing left over: it is a factor of 18. The packets ask the same of 24. So the number of parcels has to be a factor of 18 and a factor of 24. Two parcels would work, and so would three, but Tamsin wants as many parcels as she can make, so that more families get one. She needs the largest number that is a factor of both. That number is 6: six parcels, each with 3 tins and 4 packets.
Reach for this whenever two or more amounts must be split into identical shares with nothing left over, and you want the most shares or the biggest share. The same number turns up when you simplify a fraction such as \displaystyle \frac{18}{24} and when you pull a shared factor out of a sum such as 18 + 24; both come up at the end of this lesson.
The procedure
A factor list, in pairs
A factor of a whole number is a whole number that divides it with nothing left over, as in factors and multiples. To be sure of finding every factor, find them in pairs. Try 1, 2, 3 and so on in turn. Each time a number divides n, the quotient divides n too, because the two multiply back to n. So every success gives two factors at once. For 36:
5 does not divide 36, and at 6 the partner is 6 itself. Stop there. Any factor bigger than 6 needs a partner smaller than 6, because two numbers both bigger than 6 multiply to more than 36, and every number smaller than 6 has already been tried. So the list is complete:
In general, stop as soon as the number you are about to test, times itself, is more than n. The tests in divisibility by 2, 5 and 10 and divisibility by 3 and 9 make each trial quick.
Common factors
A common factor of two whole numbers is a number that is a factor of both. Write the two lists and pick out the numbers on both:
| Number | Factors |
|---|---|
| 18 | 1, 2, 3, 6, 9, 18 |
| 24 | 1, 2, 3, 4, 6, 8, 12, 24 |
The common factors of 18 and 24 are 1, 2, 3 and 6. Each is a possible number of parcels for Tamsin: 1 parcel of 18 tins and 24 packets, 2 parcels of 9 and 12, 3 of 6 and 8, or 6 of 3 and 4.
The greatest common factor
The greatest common factor of two whole numbers is the largest of their common factors. It is written \text{GCF}(18, 24), and here
Other books call it the greatest common divisor or the highest common factor; all three names mean the same number. Three facts about it, for numbers other than 0, each following straight from the definition:
- 1 is a factor of every whole number, so two numbers always have a common factor, and the GCF always exists.
- A factor of a number other than 0 is never larger than the number, so the GCF is never larger than the smaller of the two.
- Every common factor is on the smaller number’s list, so the second list can be skipped. Go down the factors of the smaller number from the top; the first one that also divides the larger number is the GCF, since every factor above it has been tried and failed.
Look at the common factors of 18 and 24 again: 1, 2, 3 and 6 are exactly the factors of 6. That is not luck. Every common factor of two numbers is a factor of their GCF. The reason comes with prime factorizations: a common factor can hold each prime only as often as both numbers do, and the GCF holds each one exactly that often. For now it is a handy check: if the GCF you found is not divisible by every common factor on your lists, something has gone wrong.
The same definition works for three or more numbers: a common factor divides all of them, and the GCF is the largest such number.
From a story to a GCF
An amount can be split into equal shares with nothing left over exactly when the number of shares is a factor of the amount. That is the whole bridge from a story to a GCF, and two kinds of question cross it.
The most identical parcels. Each parcel holds some of every item and all the parcels match. The number of parcels must divide every amount, so the most parcels is the GCF. Each parcel then holds each amount divided by the GCF.
The biggest equal groups of one kind. Each item stays in its own groups, say stacks of one kind of tin, but every group must be the same size. Now the size must divide every amount, so the biggest size is the GCF, and the number of groups is each amount divided by it.
In both, read what the question counts. The GCF answers one number and a division gives the other.
Worked examples
Two lists side by side
Find the common factors of 30 and 45, and their greatest common factor.
SolutionList each number’s factors in pairs. For 30: 1 \times 30, 2 \times 15, 3 \times 10, 5 \times 6, and stop, since 6 \times 6 = 36 is more than 30. For 45: 1 \times 45, 3 \times 15, 5 \times 9; 2, 4 and 6 fail because 45 is odd, and 7 \times 7 = 49 is more than 45.
| Number | Factors |
|---|---|
| 30 | 1, 2, 3, 5, 6, 10, 15, 30 |
| 45 | 1, 3, 5, 9, 15, 45 |
The common factors are 1, 3, 5 and 15, so \text{GCF}(30, 45) = 15. Check: 30 = 15 \times 2 and 45 = 15 \times 3, and the other common factors, 1, 3 and 5, all divide 15.
Working down the smaller list
Find \text{GCF}(48, 84).
SolutionThe GCF is a factor of 48, the smaller number, so list only those. The pairs 1 \times 48, 2 \times 24, 3 \times 16, 4 \times 12 and 6 \times 8 give
Now test them against 84 from the top, since the first one that works is the greatest. 48 fails: 84 is less than twice 48. 84 \div 24 is 3 remainder 12, and 84 \div 16 is 5 remainder 4. Then 84 \div 12 = 7 exactly, so
Every factor of 48 above 12 was tried and failed, so no common factor is larger. The longer list for 84 was never needed.
The two extreme cases
Find (a) \text{GCF}(17, 51) and (b) \text{GCF}(25, 36).
Solution(a) 17 is prime, so its only factors are 1 and 17. Test 17 first: 51 = 17 \times 3, so it divides, and \text{GCF}(17, 51) = 17, the smaller number itself. This happens whenever the smaller number divides the larger: the smaller number is then a common factor, and no common factor can be bigger than it.
(b) The factors of 25 are 1, 5 and 25. Neither 25 nor 5 divides 36, since 36 ends in neither 0 nor 5. Only 1 is left, so \text{GCF}(25, 36) = 1. Neither number is prime, yet they share no factor but 1. Two numbers whose GCF is 1 are called relatively prime.
The most identical parcels
Haruto has 42 tins of soup and 56 packets of rice. He wants to pack all of them into identical parcels with nothing left over. What is the largest number of parcels he can make, and what goes into each?
SolutionEvery parcel gets the same number of tins and every tin is used, so the number of parcels is a factor of 42. The packets make it a factor of 56 as well. The most parcels is therefore the GCF.
| Number | Factors |
|---|---|
| 42 | 1, 2, 3, 6, 7, 14, 21, 42 |
| 56 | 1, 2, 4, 7, 8, 14, 28, 56 |
The common factors are 1, 2, 7 and 14, so \text{GCF}(42, 56) = 14. Haruto can make 14 parcels, each holding 42 \div 14 = 3 tins and 56 \div 14 = 4 packets. Check: 14 \times 3 = 42 and 14 \times 4 = 56, so nothing is left over.
The smaller common factors are possible too: 7 parcels of 6 tins and 8 packets would also work, just fewer and bigger.
The tallest stacks of one kind
Adaeze is shelving 36 tins of tomatoes and 60 tins of beans. Each stack holds one kind of tin only, and every stack must be the same height. What is the tallest she can make the stacks, and how many stacks will there be?
SolutionThe two kinds do not mix, so this time the GCF will be the size of a group, not the number of groups. The tomatoes split into stacks of equal height with none over, so the height is a factor of 36; the beans make it a factor of 60 too. The tallest stack is the GCF.
Work down the factors of 36, the smaller number. 36 does not divide 60, and 60 \div 18 is 3 remainder 6, but 60 = 12 \times 5. So \text{GCF}(36, 60) = 12.
The stacks are 12 tins tall. There are 36 \div 12 = 3 stacks of tomatoes and 60 \div 12 = 5 stacks of beans, 8 stacks in all. In Haruto’s problem the GCF counted parcels; here it measures each stack.
Three kinds of item
Marco has 24 tins of fish, 40 tins of fruit and 56 packets of oats. What is the largest number of identical parcels he can pack with nothing left over?
SolutionThe number of parcels must divide all three amounts. Work down the factors of 24, the smallest amount: 24, 12, 8, 6, 4, 3, 2, 1. 24 fails, since 40 \div 24 leaves 16. 12 fails, since 40 \div 12 leaves 4. 8 works for both of the others: 40 = 8 \times 5 and 56 = 8 \times 7. So \text{GCF}(24, 40, 56) = 8.
Marco makes 8 parcels, each with 3 tins of fish, 5 tins of fruit and 7 packets of oats. Here \text{GCF}(24, 40) is already 8, and 8 happens to divide 56. Had the third amount been 60, the answer would have dropped to \text{GCF}(24, 40, 60) = 4. A third number can keep the GCF the same or make it smaller, never larger.
Working backwards from the parcels
Elif packed 60 tins and some packets into identical parcels with nothing left over, and 12 parcels was the most she could have made. She had more than 40 packets and fewer than 70. How many packets did she have?
SolutionThe packets were shared among 12 parcels with none left, so their number is a multiple of 12. Between 40 and 70 that leaves 48 and 60.
But 12 must be the greatest common factor, not just a common one. With 60 packets, \text{GCF}(60, 60) = 60, so she could have made 60 parcels. With 48: working down the factors of 48, neither 48 nor 24 divides 60 (60 \div 24 leaves 12), 16 does not either, and 12 does. So \text{GCF}(48, 60) = 12, as the story says. Elif had 48 packets.
Boundaries
The lists must be complete. Listing finds the GCF only if no factor is missing, and the missing one could be the GCF itself. Pairing, with the stopping rule, is what guarantees a complete list.
Big numbers make long lists. For numbers in the hundreds, or with many factors, listing is slow. Prime factorizations, found with Prime factorization, give the GCF more directly, and that method is its own lesson.
Zero is a special case. Every whole number other than 0 divides 0, since 0 \div n = 0 with nothing left over, so \text{GCF}(0, 12) = 12. Two zeros share all of those as factors, so there is no greatest, and \text{GCF}(0, 0) is left undefined. Stories never meet this: no one packs parcels from zero tins.
The story must ask for identical shares with nothing left over. If leftovers are allowed, or the parcels need not match, nothing forces the number of parcels to be a common factor. A question about the smallest amount that can be split both ways, or about when two repeating events next happen together, is about multiples instead: that is the least common multiple.
The GCF answers one question. It counts parcels when every parcel holds every item, and it is the group size when items are kept apart. The other number comes from a division.
Where this goes next
The least common multiple by listing is the partner idea, with multiples in place of factors, and prime factorizations find both numbers faster when lists get long.
The GCF simplifies a fraction in one step. Dividing the top and bottom of \displaystyle \frac{18}{24} by \text{GCF}(18, 24) = 6 gives the equivalent fraction \displaystyle \frac{3}{4}, and since 3 and 4 are relatively prime it cannot be simplified further.
It also pulls a shared factor out of a sum. Since 18 = 6 \times 3 and 24 = 6 \times 4,
which is the distributive property read from right to left. In Tamsin’s terms, 42 items make 6 parcels of 7 items each. Writing sums this way is the first step in writing equivalent expressions.
Exercises
Common factors
- List the common factors of 12 and 20.
- List the common factors of 27 and 45.
Greatest common factor
Find the greatest common factor by listing factors.
- 16 and 40
- 35 and 49
- 54 and 72
- 39 and 65
- 22 and 35
- 26 and 78
- 60 and 96
- 18, 30 and 42
Parcels and stacks
- Tamsin has 32 tins of peas and 48 packets of crackers. What is the largest number of identical parcels she can pack with nothing left over, and what goes into each?
- Haruto has 45 tins of soup and 75 packets of noodles. What is the largest number of identical parcels he can pack with nothing left over, and what goes into each?
- Adaeze stacks 28 tins of beans and 70 tins of tomatoes, one kind per stack, all stacks the same height. How tall can the stacks be, at most, and how many stacks are there?
- Marco has 20 tins of fish, 30 packets of rice and 50 packets of tea. What is the largest number of identical parcels he can pack with nothing left over?
- Elif has 25 tins and 33 packets. What is the largest number of identical parcels she can pack with nothing left over? What does the answer mean?
- Dev has 36 tins and 54 packets. List every number of identical parcels he could pack with nothing left over.
- Dev cuts a sheet of card 40 cm by 64 cm into identical squares, with none wasted. What is the largest side the squares can have, and how many squares does he get?
Working backwards
- \text{GCF}(24, n) = 8, and n is between 30 and 50. Find every possible n.
- \text{GCF}(n, 45) = 15, and n is less than 100. Find every possible n.
Reasoning
- Explain why two whole numbers other than 0 always have a common factor, and why their GCF is never larger than the smaller number.
- Elif says the GCF of two different even numbers is always 2. Is she right? Give an example and explain.
- Explain why, when the smaller of two numbers is a factor of the larger, the GCF is the smaller number.
- Dev has 30 tins and 48 packets. He says 3 is the most identical parcels he can make, because 3 is a common factor. What is right and what is wrong?
- Explain why working down the factors of the smaller number, and stopping at the first one that divides the larger, gives the GCF.
Answers
- 1, 2 and 4. 12: 1, 2, 3, 4, 6, 12; 20: 1, 2, 4, 5, 10, 20.
- 1, 3 and 9. 27: 1, 3, 9, 27; 45: 1, 3, 5, 9, 15, 45.
- 8. 16 does not divide 40, but 8 does: 40 = 8 \times 5.
- 7. 35: 1, 5, 7, 35; 49: 1, 7, 49.
- 18. 54: 1, 2, 3, 6, 9, 18, 27, 54; working down, 54 and 27 do not divide 72, and 72 = 18 \times 4.
- 13. 39: 1, 3, 13, 39; 65: 1, 5, 13, 65.
- 1. 22: 1, 2, 11, 22; 35: 1, 5, 7, 35. They are relatively prime.
- 26. 78 = 26 \times 3, so the smaller number divides the larger.
- 12. Common factors 1, 2, 3, 4, 6, 12; working down the factors of 60, 60, 30, 20 and 15 fail and 96 = 12 \times 8.
- 6. Common factors of all three: 1, 2, 3, 6; 18 = 6 \times 3, 30 = 6 \times 5, 42 = 6 \times 7, and 9 and 18 do not divide 30.
- 16 parcels, each with 2 tins and 3 packets. 32 does not divide 48, but 16 does.
- 15 parcels, each with 3 tins and 5 packets. 45: 1, 3, 5, 9, 15, 45; 75: 1, 3, 5, 15, 25, 75.
- 14 tins tall, with 2 stacks of beans and 5 of tomatoes, 7 stacks. 28 does not divide 70, but 14 does.
- 10 parcels, each with 2 tins of fish, 3 packets of rice and 5 packets of tea. 20 fails on 30; 10 divides all three.
- 1. \text{GCF}(25, 33) = 1, so the only way is one parcel holding all 25 tins and 33 packets.
- 1, 2, 3, 6, 9 or 18 parcels: the common factors of 36 and 54.
- 8 cm squares, 40 of them. The side must divide both 40 and 64, and \text{GCF}(40, 64) = 8; that makes 5 rows of 8.
- n = 32 or n = 40. n must be a multiple of 8: 32, 40 or 48. But \text{GCF}(24, 48) = 24.
- n = 15, 30, 60 or 75. The multiples of 15 below 100 are 15, 30, 45, 60, 75, 90, but 45 and 90 have GCF 45 with 45.
- 1 divides every whole number, so it is always a common factor. A factor of a number other than 0 is at most that number, and a common factor is a factor of the smaller number, so it is at most the smaller number.
- No. \text{GCF}(12, 20) = 4. What is true is that the GCF of two even numbers is at least 2, since 2 divides both; it can be larger.
- The smaller number divides itself and, by assumption, the larger, so it is a common factor. No common factor can be larger than the smaller number, so it is the greatest.
- 3 parcels do work (10 tins and 16 packets each), but 3 is not the greatest common factor. \text{GCF}(30, 48) = 6, so 6 parcels of 5 tins and 8 packets is the most.
- Every common factor is a factor of the smaller number, so the GCF is on that list. Going from the top, every number passed over failed to divide the larger, so it was not a common factor. The first one that works is therefore the largest common factor.