Reading HCF and LCM straight off two factorisations

0:00Two numbers, and two questions you can ask about them. First: what is the biggest number that divides both of them? Second: what is the smallest number that both of them divide into? Those are the HCF and the LCM, and notice that they pull in opposite directions. One is looking downward, for something that fits inside both. The other is looking upward, for something both of them fit inside.

0:30You have probably found them by listing. Every divisor of this, every divisor of that, and take the biggest one they share. That works. It also gets slow, and it tells you nothing about why the answer is the answer. There is a better way, and the whole of it is one idea. Here is the idea. When does one number divide another? Write them both as products of primes.

0:586 is 2 times 3. 60 is 2 times 2 times 3 times 5. Does 6 divide 60? Ask it prime by prime. 6 needs one 2, and 60 has two of them. Fine. 6 needs one 3, and 60 has one. Fine. So yes it does, and you can see the room 60 has to spare. Now try it the other way. 20 needs two 2s, and 6 has only one, so 20 cannot possibly fit inside 6.

1:32That is the entire test. One number divides another exactly when every prime index in the first is no bigger than the matching index in the second. And it never misses a case, because each number has only one factorisation for you to check. So set two numbers out in columns, one column for each prime. 6 is 2 times 3. One 2, one 3. 20 is 2 squared times 5. Two 2s, one 5.

2:05Now give them the same columns, headed 2, 3 and 5, and let each number fill in what it has. 6 has no 5 at all, so write 0 in that column. 20 has no 3, so write 0 there too. That 0 is not decoration. It is a statement: this number has none of this prime. And now the two are lined up, so every question about them has become a question about a column.

2:36Take the HCF first, and do it the slow way, so you can watch the rule appear on its own. The divisors of 6 are 1, 2, 3 and 6. The divisors of 20 are 1, 2, 4, 5, 10 and 20. Which ones do they share? 1 and 2. That is the whole list. So the biggest number dividing both of them is 2. Now go back to the columns and ask what the test demands.

3:05A common divisor has to fit inside 6, so its 2 index is at most 1. It has to fit inside 20 as well, so its 2 index is at most 2. At most 1 and at most 2 together mean at most 1. The lower of the two. There was never anything to search for. Now the LCM, the same way round. A common multiple has to be divisible by 6, so it needs at least one 2.

3:35It has to be divisible by 20, so it needs at least two 2s. At least one and at least two together mean at least two. The higher of the two. The 3 column says at least 1 and at least 0, so at least 1. The 5 column says at least 0 and at least 1, so at least 1. Take the smallest number meeting every one of those demands and you get 2 squared, times 3, times 5.

4:04Which is 60. And 60 really is the first number that both 6 and 20 divide into. Look at what just happened, because both answers came off one table. For the HCF you read the lower index down each column. For the LCM you read the higher index up each column. Same table, same columns, opposite direction. And neither of those is a rule anybody had to invent. Dividing both means fitting inside both, and fitting inside both forces the lower number.

4:42Being divisible by both means containing both, and containing both forces the higher one. The two rules are one sentence, read once downward and once upward. Before going on, kill an idea that looks reasonable and is wrong. It is tempting to think the HCF comes out of the smaller number and the LCM out of the bigger one. Look again at 6 and 20. The HCF is 2, and that 2 came from the 6, which is the smaller one and had only a single 2 in it.

5:20The two 2s in the LCM came from the 20, the bigger one. But the 3 in the LCM came from the 6, and the 5 came from the 20. Every column is settled entirely on its own. Nothing whatever is decided per number. And the prime they share is not always the 2. 26 is 2 times 13. 91 is 7 times 13, and 91 is not even at all.

5:50The only column with two entries in it is the 13. So the HCF is 13, and the LCM is 2 times 7 times 13, which is 182. A pair can share a large prime and share nothing small. The 0 column is where this really pays, so look at it properly. 6 has no 5. Its 5 index is 0. For the HCF you take the lower of 0 and 1, which is 0.

6:23So 5 contributes nothing. And it could not have, because 6 is not divisible by 5, so nothing carrying a 5 can divide 6. For the LCM you take the higher of 0 and 1, which is 1. So 5 contributes in full. And it had to, because the answer must be a multiple of 20, and 20 carries a 5. One column, one 0, and it settles both questions in opposite directions.

6:55That is why the HCF uses only the primes they share, while the LCM uses every prime in sight. Try it on a pair you would not want to list. 96 is 2 to the fifth, times 3. 404 is 2 squared, times 101. And 101 is prime, so that is as far as it goes. Three columns: 2, 3 and 101. The 2 column holds 5 and 2. Lower is 2, higher is 5.

7:30The 3 column holds 1 and 0. Lower is 0, higher is 1. The 101 column holds 0 and 1. Lower is 0, higher is 1. So the HCF is 2 squared, which is 4. And the LCM is 2 to the fifth, times 3, times 101, which is 9696. Two stranded primes, one in each number, and neither goes anywhere near the HCF. Now the part that costs nothing at all. A third number.

8:076, 72 and 120. 6 is 2 times 3. 72 is 2 cubed times 3 squared. 120 is 2 cubed times 3 times 5. Three rows instead of two, and the columns do not change. The 2 column reads 1, 3, 3. Lowest is 1, highest is 3. The 3 column reads 1, 2, 1. Lowest is 1, highest is 2. The 5 column reads 0, 0, 1. Lowest is 0, highest is 1.

8:44So the HCF is 2 times 3, which is 6, and the LCM is 2 cubed, times 3 squared, times 5, which is 360. Nothing about the reasoning changed. It never does. What happens if two numbers share nothing at all? 17, 23 and 29 are three different primes. Three columns, and each number has a 1 in its own column and a 0 in the other two. The lowest entry in every column is 0, so the HCF is 1.

9:21The highest in every column is 1, so the LCM is all three multiplied together: 11339. And this is not really about being prime. Take 8, 9 and 25. Not one of those is a prime number. But 8 is nothing but 2s, 9 is nothing but 3s, and 25 is nothing but 5s, so no column has more than one entry in it. HCF 1 again, and the LCM is again just the product.

9:57Sharing nothing is a statement about columns, not about being prime. Now here is what the columns are actually worth. Take 510 and 92. Hunt for their LCM by listing multiples of 510, and you write 46 of them before one is also a multiple of 92. List multiples of 92 instead and you write 255 of them. Both routes do arrive, at 23460. The columns get there in 5 steps, because 5 different primes appear across the pair: 2, 3, 5, 17 and 23.

10:43And only the 2 is in both of them. The listing cost grows with the size of the answer. The column cost is just how many different primes are in front of you. Bigger numbers do not mean more columns. They usually mean bigger indices, and comparing a big index is no harder than comparing a small one. Finally, what any of this is for. Ana and Ben are riding round the same circular track. They start together, and they go the same way round.

11:19Ana takes 18 minutes to complete a lap. Ben takes 12. When are they both back at the start line at the same moment? It has to be a whole number of laps for Ana, so a multiple of 18. And a whole number of laps for Ben, so a multiple of 12. The first moment that is both of those is the LCM. 18 is 2 times 3 squared. 12 is 2 squared times 3.

11:47Higher index in each column gives 2 squared times 3 squared, which is 36. After 36 minutes Ana has ridden 2 laps and Ben has ridden 3, and there they both are. Not the HCF. The HCF of 18 and 12 is 6, and after 6 minutes neither of them has finished a lap. The question decides which one you want. The columns hand you either.