LCM: take the most occurrences of each prime

0:00Two paper chains, hanging side by side. One is built from links six centimetres long, the other from links eight. Whole links only. You cannot cut one in half. And the two chains have to finish at exactly the same length. So that length has to be something six can reach, laying links end to end. And the very same length has to be something eight can reach. It has to be a multiple of both — a common multiple problem, before anybody says the words.

0:34And of the lengths that work, we want the shortest, because a shorter chain is less work. So climb the two ladders and see where they meet. Six, twelve, eighteen, twenty-four, thirty, thirty-six, forty-two, forty-eight, fifty-four. Eight, sixteen, twenty-four, thirty-two, forty, forty-eight, fifty-six, sixty-four, seventy-two. Twenty-four is on both ladders. That is four of the six-centimetre links, and three of the eight. Keep climbing and forty-eight is on both as well.

1:10So there is more than one answer, and the shortest is twenty-four. Notice what forty-eight is, though. Six times eight. Multiplying the two lengths always gives a length both chains can reach, just not the shortest. There is a question hiding here, better than it looks. We asked for the shortest length. Is there a longest? Let the ladders keep climbing. Twenty-four, forty-eight, seventy-two, ninety-six, a hundred and twenty, a hundred and forty-four.

1:45Every twenty-four, going up forever. And here is why it never stops. Take any length that works, and double it. If six fits into that length a whole number of times, it fits into twice it too. So does eight. So whatever answer you name, twice that is another. There is no largest. Which is why the shortest is the interesting end of the list — it is the only end there is.

2:15The same problem turns up wearing different clothes. A bakery gives away a free loaf every Monday. That is every seven days. A friend of yours passes through town every ten days. Today is a Monday, she is here, and has just had a loaf. When does that happen again? Loaves on days seven, fourteen, twenty-one, twenty-eight, thirty-five, forty-two, forty-nine, fifty-six, sixty-three, seventy. Visits on days ten, twenty, thirty, forty, fifty, sixty, seventy.

2:51Day seventy. Ten loaves later, seven visits later. And seven times ten is seventy — here the product really is the answer. That shortest chain, and that seventieth day, have a name. The smallest number both of your numbers divide into is called the lowest common multiple. You will hear it called the least common multiple too. Same quantity. And the word lowest is doing real work. Hunting for common factors we wanted the highest, and a highest exists because a factor is never bigger than what it divides. That list has a top.

3:33Common multiples run the other way. They climb forever, so there is no top at all. The only end that list has is the bottom. The two ideas are mirror images, and even their names mirror. Highest for one. Lowest for the other. Here it is once more, as a game. You count around a circle. One, two, three, and so on. Land on a multiple of four and you say apple instead of the number. Land on a multiple of six and you say banana.

4:07The first person saying both words stands on the first number that is a multiple of four and of six. That is twelve, which is the lowest common multiple. Not a coincidence — it is the same question asked out loud. Seven and eleven give seventy-seven. You count a long way round for that one. Fourteen and thirty give two hundred and ten. Fifteen and fifty-five give a hundred and sixty-five.

4:38Which is where listing hurts. Reaching two hundred and ten takes fifteen multiples of fourteen and seven of thirty, and one slip gives the wrong answer. So do to multiples what we did to factors. Stop listing, start building. The key is one observation about what a multiple is made of. Take thirty-six, which is two, two, three, three. And take six hundred and forty-eight, which is thirty-six times eighteen.

5:11Write eighteen as its primes, two, three, three, and put the rows together. Six hundred and forty-eight is two, two, two, three, three, three, three. Look at what is sitting inside that row. Two, two, three, three. The whole of thirty-six, with a two and two threes left over. That is what being a multiple means. A multiple's row of primes holds the other number's entire row, and then some.

5:41Now turn that into a method. Fourteen is two times seven. Thirty-five is five times seven. We want the smallest number whose row holds both of those rows at once. It needs a two, because fourteen has one. A five, because thirty-five has one. And a seven. Two, five, seven. That is seventy. Does it hold fourteen? A two and a seven — yes. Thirty-five? A five and a seven — yes.

6:12And nothing in it is spare. Take the five out and you have fourteen, which cannot hold thirty-five. Take the two out and you have thirty-five, which cannot hold fourteen. Every prime in seventy is there because one of the two demanded it. That is what makes it the lowest. Now a pair you could not do by eye. Ninety-six is two, two, two, two, two, three. Three hundred and sixty is two, two, two, three, three, five.

6:44Go prime by prime and count, but ask the opposite question. Twos: ninety-six has five, three hundred and sixty has three. We need five — anything with fewer cannot hold ninety-six. Threes: ninety-six has one, three hundred and sixty has two. We need two. Fives: ninety-six has none at all, three hundred and sixty has one. We still need one. That last line is the one to watch. Five is in only one of the two numbers and still has to be in the answer — without it, the result is not a multiple of three hundred and sixty.

7:26Five twos, two threes and one five. That is one thousand four hundred and forty. Why the larger count, and not the smaller? For common factors we took the smaller, and taking more made the answer stop fitting inside one of them. Here the failure runs the other way. Take four twos instead of five and you get seven hundred and twenty. That is a fine multiple of three hundred and sixty. But ninety-six does not divide it — you get seven and a half.

8:02There are five twos inside ninety-six, and four cannot hold five. So a prime here is not capped by the smaller count. It is demanded by the larger one. Too many copies and you fall out of one of the numbers. Too few and you fail to hold one. The whole difference is one word. Smaller becomes larger. The other direction is far more forgiving. Go back to fourteen and thirty-five, where the answer was seventy.

8:34Throw an extra three in. Two, three, five, seven, which is two hundred and ten. That still holds fourteen and still holds thirty-five. Still a common multiple, simply bigger than it needs to be. Or two, seven, five, seven and three, which is one thousand four hundred and seventy. Both are correct answers to what is a common multiple. Neither answers what we asked. Which brings back the shortcut everybody reaches for. Just multiply the two numbers.

9:10Never wrong — the product is always a common multiple. It just counts the shared primes twice. Six times eight is forty-eight, and the two they both own got counted in both, which is why the answer is half of that. The rule, then, in one line. Write your numbers as primes. For every prime appearing in any of them, take the largest count you see. Multiply. And it does not care how many numbers you hand it.

9:43A hundred and five is three, five, seven. A hundred and ninety-five, three, five, thirteen. Sixty-five, five and thirteen. One three, one five, one seven, one thirteen. That is one thousand three hundred and sixty-five. Seven is in only one of the three and still has to be there. A prime only has to be demanded by somebody. One to finish on. A herd goes through three gates in equal numbers, then five, then seven.

10:17So the herd is a multiple of three, of five and of seven. One of each, a hundred and five. The next one up is two hundred and ten, so under two hundred that is the only herd there is.