Reading every factor of a number off its prime factorisation

0:00Is twenty-eight a factor of eight hundred and forty? You could divide and see. That works, and it teaches you nothing. It answers this one question and leaves you no better placed for the next one. So here is a better way, and it turns out to answer a far larger question at the same time. Take the prime factorisation of eight hundred and forty. Two, two, two, three, five, seven. Six primes.

0:30That is the whole of eight hundred and forty. There is nothing else in it. And the claim we are going to earn is this: every factor it has is a piece cut out of that row. Start with the one question we were asked. Twenty-eight is two times two times seven. So look along the row and see whether those are in it. A two, yes. Another two, yes, there are three of them. A seven, yes.

0:58Now slide the ones you took to one side. Two, two and seven on the left. Two, three and five on the right. Nothing was added and nothing thrown away. The primes were only reordered, and reordering never changes a product. So eight hundred and forty is twenty-eight times thirty, and twenty-eight is a factor. No division happened anywhere. Look at what arrived alongside the answer. You asked about twenty-eight, and you were handed thirty as well.

1:33That is not a bonus. It is unavoidable. The primes you cut out make one number. The primes left behind make the other. Between them they use every prime in the row exactly once, so multiplying the two gives the whole thing back. Which means factors always arrive in pairs, and pulling one out names the other for nothing. Two, two, seven leaves two, three, five. Twenty-eight leaves thirty. Every question of this kind answers two things at once, and you still never divide.

2:11Now three quick ones, all on the same number. Is two times seven a factor of eight hundred and forty? A two and a seven, both in the row. Yes. And the leftovers say its partner is sixty. Is two times two times two a factor? That wants three twos, and the row holds exactly three. Yes, with a hundred and five left over. Now this one. Is three times three times three a factor?

2:41That wants three threes. Look along the row. There is one. You take it, then you reach for another, and there is nothing there. It runs out. So twenty-seven is not a factor, and again you never divided. Now turn the idea round, because it is worth far more than these one-off questions. We have been checking candidates that were handed to us. Suppose instead we generate them. Cut out every possible piece of the row, multiply each piece together, and collect the results.

3:17Would that list be all the factors? Or only some of them? Half of that is easy, and we have already done it three times. Any piece you cut out is a factor, because the leftovers are sitting there ready to make up the difference. So everything on that list certainly belongs on it. The hard half runs the other way. Could there be a factor that never appears on the list at all?

3:45This is the step worth slowing down for, because it is where the real work happens. Suppose some number divides eight hundred and forty but is built out of a prime the row does not contain. Eleven, say. Then eight hundred and forty is that number times something else. Break both of those into primes, and you have just written eight hundred and forty as a product of primes with an eleven sitting in it.

4:14But a number has only one prime factorisation. And eight hundred and forty's has no eleven, so the number we supposed cannot exist. Nothing from outside can get in. The row is the entire supply. Which is why it mattered so much that the factorisation is forced. This whole method is standing on it. So let us do it properly, and list every factor a number has. Two hundred and twenty-five. Divide by five, and by five again. Then by three, and by three.

4:51Three, three, five, five. Four primes. Now work through the pieces by how many primes they use. One at a time: three, and five. Two at a time: three and three make nine, three and five make fifteen, five and five make twenty-five. Three at a time: three, three and five make forty-five. Three, five and five make seventy-five. And all four at once, which is two hundred and twenty-five itself.

5:23That is eight factors. Three, five, nine, fifteen, twenty-five, forty-five, seventy-five and two hundred and twenty-five. One is missing, and the one that is missing is one. One divides everything, so it is certainly a factor. But it is not built out of any of the primes in the row. So where is it supposed to come from? Go back to how we organised the search. One at a time, two at a time, three, four.

5:54We never did none at a time. Take no primes at all, multiply nothing together, and what you have is one. So it is not an exception being smuggled in at the end. It is the first line of the table, and the finished list has nine. Now a trap, and it is the one that ruins these counts. Two hundred and twenty-five has four prime factors. Three, three, five, five.

6:23How many ways are there of picking two things out of four? Six. But we only found three numbers on that line. Nine, fifteen and twenty-five. The reason is that the two threes are not two different things. They are both just three. Take the first three with the second five and you get fifteen. Take the second three with the first five and you get fifteen again. Six selections, three answers. The repeats collapse.

6:54Any count that treats identical primes as though you could tell them apart comes out too big, and that is much the commonest way to get these wrong. Look at the shape of what we found. None at a time, one. One at a time, two. Two at a time, three. Three at a time, two. Four at a time, one. One, two, three, two, one. It reads the same forwards and backwards.

7:22That is not a coincidence, and you already know the reason. Every piece you cut out leaves a partner behind. Take one prime and you leave three of them. Take two and you leave two. So the line for one and the line for three must be the same length, because their entries are paired off one to one. And the entry in the middle, fifteen, is its own partner. Fifteen times fifteen is two hundred and twenty-five.

7:53Try it on a few of your own. Ninety is two, three, three, five. A hundred and five is three, five, seven. A hundred and thirty-two is two, two, three, eleven. Three hundred and sixty is two, two, two, three, three, five. Enumerate those and you get twelve factors, then eight, then twelve, then twenty-four. And eight hundred and forty, where we started, has thirty-two. Once you have done a few, a shortcut turns up on its own.

8:26Count how many times each prime repeats, add one to every count, and multiply those numbers together. Three hundred and sixty has three twos, two threes and one five. Four times three times two is twenty-four. The added one is the choice of not taking that prime at all. One last thing, and it is about a very tempting idea. Here it is. The bigger the number, the longer its prime factorisation.

8:59It sounds obviously right. Bigger numbers ought to be built out of more. Ninety-six is two, two, two, two, two, three. Six primes. A hundred and twenty-one is eleven times eleven. Two primes. A hundred and twenty-one is the larger number, with the shorter row, and only three factors against ninety-six's twelve. One example is enough to sink a claim of that shape, and it is worth noticing how cheap the sinking was.

9:31The method itself survives untouched, because it never cared how big the number was. It only ever cared what the row said. Which is exactly what you want when you start asking what two numbers have in common.