HCF: take the fewest occurrences of each prime

0:00A room, twelve feet by sixteen. You are tiling it with square tiles, all the same size, and the side has to be a whole number of feet. You would like as few tiles as possible, because fewer tiles is less work. So how big can the tile be? Try three feet. Three goes into twelve four times, so that edge is fine. But sixteen divided by three leaves one foot over, and you would have to cut a tile.

0:31So the side has to divide twelve exactly, and it has to divide sixteen exactly. It has to be a factor of both. That is what makes this a common factor problem, before anybody says the words. The factors of twelve are one, two, three, four, six and twelve. The factors of sixteen are one, two, four, eight and sixteen. Read those against each other and three sizes work. One foot, two feet, four feet.

1:04Now, which do we want? The question said as few tiles as possible. A one-foot tile needs a hundred and ninety-two of them. A two-foot tile needs forty-eight. A four-foot tile needs twelve. Three along one wall and four along the other. So bigger tile, fewer tiles. Wanting the fewest is the same as wanting the largest side, which is why we want the largest common factor and not just any of them.

1:37That thing has a name. The largest number that is a factor of both is called the highest common factor. You will also see it called the greatest common divisor. Same quantity, two names. And the same problem turns up wearing different clothes. Eighty-four kilograms of rice from one farm, a hundred and eight from another. Pack them into bags of equal whole weight, never mixing the farms, using as few bags as you can.

2:08The common factors of eighty-four and a hundred and eight are one, two, three, four, six and twelve. Twelve kilograms a bag. Seven bags from the first farm, nine from the second, sixteen in all. Or here it is again as a game. You start at zero on a number line and take equal jumps forward, and there is treasure at two places. How long can your stride be if you want to land on both?

2:39Treasure at fourteen and thirty. Strides of one and two work, and nothing else does. Treasure at thirty and fifty: one, two, five, or ten. Twenty-eight and forty-two: one, two, seven, or fourteen. And seven and eleven, where the only stride that works is a single step at a time. The longest usable stride is the highest common factor every single time, and it has to be, because a stride that lands on a number is a factor of it.

3:13So far we have found these by listing. Write out all the factors of one number, all the factors of the other, and read the two lists against each other. It works, and it will not keep working. Eighty-four has twelve factors, and you had to find every one to use six of them. Push the numbers up and the lists get long, and long lists are where entries quietly go missing.

3:39There is also something unsatisfying about it. You searched, and then hoped you had not missed anything. So let us stop searching and start building. And the tool for that is the one we already have: every factor of a number is a piece cut out of its prime factorisation. Here is the reframing, and everything else follows from it. A common factor has to be a piece cut out of the first number's factorisation.

4:10And the very same number has to be a piece cut out of the second one's. So take forty-five and seventy-five. Forty-five is three, three, five. Seventy-five is three, five, five. Can we find a three in both? Yes. So three is a common factor. A five in both? Yes. And a three and a five together in both? Also yes, so fifteen is a common factor. With one, that is the complete list: one, three, five, fifteen. And the highest is fifteen.

4:46Do it again on a bigger pair and you will feel the method straining. A hundred and twelve is two, two, two, two, seven. Eighty-four is two, two, three, seven. A single two matches. So does a single seven. Two twos match, because both numbers have at least two of them. A two and a seven together match. And two twos and a seven together match. That is five pieces, plus one, so six common factors in all.

5:17The largest is two times two times seven, which is twenty-eight. Correct, and slow. We hunted for pieces one at a time and then hoped the biggest one we found was the biggest there was. Before we fix that, here is the case where the hunting stops immediately. Ninety-six is two, two, two, two, two, three. Two hundred and seventy-five is five, five, eleven. Look for a piece of one inside the other and there is nothing.

5:50Not a single prime appears in both rows. So there is no piece to match at all, and the only common factor is one. Which makes one the highest common factor too. And notice that is not the same as having no common factor. One is a factor of everything, so it is always there, sometimes on its own. Now the fix, and it turns the whole thing from a search into a calculation.

6:20Take thirty and seventy-two. Thirty is two, three, five. Seventy-two is two, two, two, three, three. Go prime by prime and just count. Twos: thirty has one, seventy-two has three. So the most we can take is one, because thirty has run out. Threes: thirty has one, seventy-two has two. Again we can take one. Fives: thirty has one, seventy-two has none at all, so we take nothing. One two and one three. The highest common factor is six, and we never listed a single factor.

6:59It is worth being sure about why we stop there. Why not take two twos, since seventy-two has three of them going spare? Because then the answer would have to be four times something, and four does not divide thirty. Thirty divided by four leaves two over. It would not be a factor of thirty, so it would not be a common factor at all. The word highest attaches to the finished number, not to how many of each prime you grab.

7:30Every prime is capped by whichever of the two owns fewer of it, and taking one more always breaks it. Take everything up to the cap and you have a factor of both. Take anything beyond the cap and you have a factor of neither. So the answer is forced. There is nothing left to search. One more, because it shows something the small examples hide. Two hundred and twenty-five is three, three, five, five. Seven hundred and fifty is two, three, five, five, five.

8:05The threes: two hundred and twenty-five has two, seven hundred and fifty has one. So one three. The fives: two hundred and twenty-five has two, seven hundred and fifty has three. So two fives. Look at where those ceilings came from. The bigger number set the limit on the threes. The smaller one set the limit on the fives. There is no number that is always the mean one. The comparison happens separately for every prime.

8:37One three and two fives is seventy-five. And the same procedure handles three numbers, or thirty: keep whatever appears in all of them, take the smallest count you see. Last, a question designed to catch you, and it is worth being caught by. Seventy-two is six times twelve. A hundred and forty-four is eight times eighteen. Six, twelve, eight, eighteen. Nothing on the left matches anything on the right. So do those two numbers share no factor bigger than one?

9:14They share seventy-two. Seventy-two divides a hundred and forty-four exactly twice. But we made exactly this argument a moment ago about ninety-six and two hundred and seventy-five, and it was fine there. The difference is that those were split into primes, and these are not. Six and eight share a hidden two; twelve and eighteen share a hidden six. Pieces can only be compared once they have been broken down as far as they go. Split both into primes and seventy-two and a hundred and forty-four turn out to share three twos and two threes, which is seventy-two exactly.