Gears, lockers and common factors
Tonight's idea
Every whole number bigger than 1 has a prime recipe, its list of prime factors (see Primes and the Sieve). \(84 = 2^2 \cdot 3 \cdot 7\) and \(120 = 2^3 \cdot 3 \cdot 5\). From the recipes, two numbers fall out:
Greatest common factor (GCF): the biggest number dividing both. Take each prime to the smaller power it appears with: \(2^2 \cdot 3 = 12\).
Least common multiple (LCM): the smallest number both divide into. Take each prime to the larger power: \(2^3 \cdot 3 \cdot 5 \cdot 7 = 840\).
Check: \(\text{GCF} \times \text{LCM} = 84 \times 120\). Both are 10 080. Every prime goes into one or the other, so the product is the same. Knowing one, you can find the other by dividing.
Euclid's trick is faster and needs no primes: the GCF of two numbers is the same as the GCF of the smaller one and the remainder when you divide. Any number dividing 120 and 84 must divide the leftover \(120 - 84 = 36\), and so on down. Keep taking remainders until you hit 0. The last number you divided by is the GCF.
Watch one
GCF of 120 and 84 by Euclid. \(120 = 1 \times 84 + \mathbf{36}\): remainder 36, so now find GCF(84, 36). \(84 = 2 \times 36 + \mathbf{12}\): remainder 12, so now GCF(36, 12). \(36 = 3 \times 12 + 0\): remainder 0, stop. The last nonzero remainder is 12, so GCF \(= 12\).
Gears with 12 and 18 teeth, marked teeth touching. The marks meet again after a number of teeth that is a multiple of both 12 and 18: the LCM, 36.
Your turn
- Find the GCF and LCM of 36 and 48, then of 45 and 75. Check that GCF × LCM equals the product each time.
- Run Euclid's algorithm on 252 and 198. Write every line.
- Buses on route A leave every 12 minutes, route B every 18 minutes, route C every 20 minutes. All three leave together at 8:00. When do all three next leave together?
- A floor is 84 cm by 60 cm. What is the largest square tile that covers it exactly, and how many tiles are needed?
- Two numbers have GCF 6 and LCM 180. One of them is 30. What is the other? (Use the product fact.)
- Why does Euclid's method work? Explain in two sentences why any number that divides both 120 and 84 must also divide 36.
Stretch: a thousand lockers
A school has 1000 lockers, all closed, and 1000 students. Student 1 opens every locker. Student 2 closes every second locker. Student 3 changes every third locker (opens it if closed, closes it if open). Student \(k\) changes every \(k\)th locker. After all 1000 students, which lockers are open, and how many?
Hints. Locker \(n\) is touched once for each divisor of \(n\). It ends open if it is touched an odd number of times. Divisors come in pairs, \(d\) and \(n/d\), so when does a number have an odd number of divisors? Try lockers 12, 16 and 36 by hand first.
Answers
- 36 and 48: \(36 = 2^2 \cdot 3^2\), \(48 = 2^4 \cdot 3\); GCF 12, LCM 144; \(12 \times 144 = 1728 = 36 \times 48\). 45 and 75: \(45 = 3^2 \cdot 5\), \(75 = 3 \cdot 5^2\); GCF 15, LCM 225; \(15 \times 225 = 3375 = 45 \times 75\).
- \(252 = 1 \times 198 + 54\); \(198 = 3 \times 54 + 36\); \(54 = 1 \times 36 + 18\); \(36 = 2 \times 18 + 0\). GCF 18.
- LCM(12, 18, 20) \(= 2^2 \cdot 3^2 \cdot 5 = 180\) minutes = 3 hours. 11:00.
- GCF(84, 60) = 12 cm tiles. \(7 \times 5 = 35\) tiles.
- \(6 \times 180 \div 30 = 36\). Check: GCF(30, 36) = 6 and LCM = 180.
- If a number \(g\) divides both 120 and 84, then 120 and 84 are both whole multiples of \(g\), and the difference of two multiples of \(g\) is still a multiple of \(g\). So \(g\) divides 36. The same reasoning works at every step, so the common factors never change, and at the end the GCF is sitting there on its own.
Stretch. Locker 12 has divisors 1, 2, 3, 4, 6, 12 (six of them, three pairs): closed. Locker 16 has 1, 2, 4, 8, 16 (five; the pair for 4 is 4 itself): open. Locker 36: 1, 2, 3, 4, 6, 9, 12, 18, 36 (nine): open. A number has an odd number of divisors exactly when it is a perfect square, because only then does one divisor pair with itself. Open lockers: \(1, 4, 9, \ldots, 961 = 31^2\). Thirty-one lockers.