Reading co-primality and divisibility straight off the prime factorisation

0:00Last time we left a question hanging. Are fifty-six and sixty-three co-prime? We couldn't settle it by hunting for factor pairs, because we could never tell when we'd found them all. Now we can write each number as its primes, and the whole question changes shape. Fifty-six is two times two times two times seven. Sixty-three is three times three times seven. Look at the two lists. Do they have anything in common?

0:31Take a second and decide before I say. There's the seven, sitting in both lists, in plain sight. So seven divides fifty-six, and seven divides sixty-three. They are not co-prime. And notice what just happened. We didn't search for anything. We wrote two lists and looked at them. That's the whole test. Compare that to last time, when we split fifty-six as fourteen times four and the seven was hidden inside the fourteen.

1:04Prime lists have nowhere to hide anything. Every prime is out on the surface. Now a pair that shares nothing. Eighty and sixty-three. Eighty is two times two times two times two times five. Sixty-three is three times three times seven. So eighty is built from twos and a five. Sixty-three from threes and a seven. Two, five, three, seven. Not one of them appears in both lists. So eighty and sixty-three are co-prime.

1:39But wait. The textbook stops here and raises an objection of its own, and it's a very good one. We only compared primes. What if the two numbers share a factor that isn't prime? Some composite number, quietly dividing both, that we'd never see by looking at primes. If that could happen, then this whole test is just a hopeful guess, not a proof. It's the one thing standing between the method and being useless. So let's settle it.

2:12Suppose some number divides both. Call it the sneaky one. If it's prime, we'd see it immediately. It would be in both lists. So say it's composite. But every composite number is built out of primes. That's what the last video was about. So pick any prime inside our sneaky number. Say the sneaky number is six, and pick the three. If six divides both of our numbers, then three divides both of them too.

2:43And that three has to appear in both prime lists. So a composite common factor can't hide. It drags its own primes into both lists with it. Which means if the prime lists share nothing, there is no common factor at all. The test is finished. It isn't a hopeful check that might have missed something. It's a proof. Let's use it. Are forty and two hundred and thirty-one co-prime?

3:12Forty is two times two times two times five. Two hundred and thirty-one is three times seven times eleven. Twos and a five, against a three, a seven and an eleven. Nothing in common. Co-prime. And that took about ten seconds, with no searching at all. One more. Two hundred and forty-two, and one hundred and ninety-five. Two hundred and forty-two is two times eleven times eleven. One hundred and ninety-five is three times five times thirteen.

3:49Careful here. The eleven appears twice in that first list. But eleven is still one prime factor. Written twice, counted once as a prime factor. So the prime factors are two and eleven, against three, five and thirteen. Nothing shared. Co-prime. Now a second question, and the same trick answers it. Instead of asking what two numbers share, let's ask whether one divides the other. Forty-eight divided by twelve is four, with nothing left over. So forty-eight is divisible by twelve.

4:30But that took a division. Can we see it from the prime lists instead? Yes, and here's the rule. One number is divisible by another when the smaller one's prime list sits inside the bigger one's. And the word doing the work there is inside. Not overlaps. Not shares something. Inside. Every prime, with every copy of it, has to be there. Let's try it. Is one hundred and sixty-eight divisible by twelve?

5:02One hundred and sixty-eight is two times two times two times three times seven. Twelve is two times two times three. So we need two twos and a three. Does the big list have them? Two twos, yes. A three, yes. It fits inside. So twelve divides one hundred and sixty-eight. And here's the lovely bit. Slide those three primes together. Two times two times three is twelve. And what's left over is two times seven, which is fourteen.

5:36So one hundred and sixty-eight is twelve times fourteen. The test didn't just say yes. It handed us the answer to the division as well. Now one that fails, in the easy way. Is seventy-five divisible by twenty-one? Seventy-five is three times five times five. Twenty-one is three times seven. We need a three and a seven. There's the three. But where's the seven? There is no seven anywhere in seventy-five. So it doesn't fit inside, and twenty-one does not divide seventy-five.

6:16A prime was simply missing. That one's easy to spot. And now the one that catches almost everybody. Is forty-two divisible by twelve? Forty-two is two times three times seven. Twelve is two times two times three. Check the primes in twelve. It needs a two. Forty-two has a two. It needs a three. Forty-two has a three. So every prime in twelve appears in forty-two. Does that settle it? It looks like it should.

6:50But it doesn't. Twelve needs two twos, and forty-two only has one. So the list doesn't fit inside. It overlaps, but it doesn't fit. And sure enough, forty-two divided by twelve is three and a half. It doesn't divide. This is the half people drop. It isn't enough that the primes are present. You have to count the copies. So here's the whole chapter, in two lines. Two numbers are co-prime when their prime lists share nothing.

7:23One number divides another when its prime list sits inside the other's, copies and all. Two questions that used to need searching. Now they're questions of looking. Before you go, try guessing these before you check. Is thirty-six divisible by nine? Are forty-nine and sixty-four co-prime? And here's one worth thinking about properly. Take any two different primes, like seven and thirteen. Are they always co-prime? They are, and the reason is almost too simple. Each list is one number long, and the two numbers are different.

8:03So now the harder version. What if the two primes are the same? Seven and seven. Think about what that does to the lists, and tell me in the comments.