Co-prime pairs, and why sharing no factor is what matters

0:00Let's play the hiding game, with one new rule. I hide two treasures. You pick a hop length and keep it, and you have to land on both. The new rule is this. You are not allowed to hop in ones. Without that rule you'd always win by walking, one step at a time, over everything. So. If I hide my treasures on twelve and twenty-six, can you catch them both?

0:26And if I hide them on four and nine, can you catch those? One of those hiding places is safe and one is not. Decide which, before I tell you. Twelve and twenty-six. Let's see. Try hopping in twos. Two, four, six, eight, ten, twelve. Got the first one. Keep going. Fourteen, sixteen, eighteen, twenty, twenty-two, twenty-four, twenty-six. Got the second one. So a hop of two catches both, and my hiding place is broken.

1:01Why did two work? Look at the factor lists. The factors of twelve are one, two, three, four, six and twelve. The factors of twenty-six are one, two, thirteen and twenty-six. They both contain two. That shared factor is exactly the hop that catches them both. One shared factor above one is all it takes. Now four and nine. Try twos. Two, four. Got the first one. But then six, eight, ten. Two steps right over nine.

1:36Try threes. Three, six, nine. Got the second one, but three skipped straight past four. Try fours, and you miss nine. Try nines, and you miss four. Nothing works. Four and nine is a safe hiding place. And here are the factor lists. Four has one, two and four. Nine has one, three and nine. The only thing they share is one, and hopping in ones is banned. So there is no hop left that reaches both.

2:07Now notice something strange. Four is not prime. Nine is not prime. Neither of them is prime. A pair like that, sharing nothing but one, gets a name. We call them co-prime. And that name is a trap, because it sounds like it means both numbers are prime. It doesn't. Four and nine are co-prime, and neither one is prime. What the word actually records is that there is nothing to divide them both with, apart from one.

2:40That's all. No shared factor above one. Here's the part people find hardest, and it's worth slowing down for. Being co-prime is not something a number is. It's something a pair is. Ask me, is nine co-prime? I can't answer. The question doesn't mean anything on its own. Nine and four? Co-prime. They share nothing. Nine and six? Not co-prime. They both have three. Same nine. Different partner. Different answer.

3:14And the same goes the other way. Having a prime in the pair doesn't make it co-prime. Three and nine. Three is prime. But three divides nine, so they share three, and the pair is not co-prime. A prime is co-prime to everything it doesn't divide, and to nothing it does. Let's judge four pairs. List the factors first, every time. That habit is the whole method. Fifteen and thirty-nine.

3:45Fifteen has one, three, five, fifteen. Thirty-nine has one, three, thirteen, thirty-nine. They share three. Not co-prime, and a hop of three catches both. Four and fifteen. Four has one, two, four. Fifteen has one, three, five, fifteen. Nothing shared but one. Co-prime. Safe. Eighteen and twenty-nine. Twenty-nine is prime, and it doesn't divide eighteen. So the only thing they share is one. Co-prime. Safe. Twenty and fifty-five. Twenty has one, two, four, five, ten, twenty. Fifty-five has one, five, eleven, fifty-five.

4:29They share five. Not co-prime. Two safe out of four. Five more, a bit quicker. Eighteen and thirty-five. Eighteen is built from twos and threes. Thirty-five is five times seven. Nothing in common. Co-prime. Fifteen and thirty-seven. Thirty-seven is prime and doesn't divide fifteen. Co-prime. Thirty and four hundred and fifteen. Both end in a zero or a five, so both have five in them. Not co-prime. Seventeen and sixty-nine. Seventeen is prime. Sixty-nine is three times twenty-three. Seventeen isn't in there. Co-prime.

5:17And eighty-one with eighteen. Eighty-one is nine times nine. Eighteen is nine times two. They share nine. Not co-prime, and both of them are composite. So there it is, twice over. Two composites can be co-prime, like four and nine. And two composites can fail to be, like eighty-one and eighteen. The word tells you about the pair, and nothing about either number alone. Now let's connect this back to the counting game from the first video.

5:51Two rhythms, counting together. Where do they first collide? Take four and nine, our co-prime pair. Multiples of four. Multiples of nine. The first number in both lists is thirty-six, and four times nine is thirty-six. The first collision landed exactly on the product. Now take twelve and twenty-six, which share a two. Twelve times twenty-six is three hundred and twelve. But they actually collide at one hundred and fifty-six, which is only half as far.

6:27So the shared factor pulled the meeting point closer. And that's the rule. When a pair is co-prime, the first collision is the product, and it can't come any sooner. When they share something, the meeting happens early. Here's the same idea again, in a shape you can see. Draw a circle and space some pegs evenly around it. Tie a thread to one peg. Then carry it forward a fixed number of pegs, tie it again, and keep going with that same gap.

7:00Twelve pegs, and a gap of four. Tie at twelve, then four, then eight, then back to twelve. It closes after three ties, and we get a triangle. It touched three pegs out of twelve, and missed nine of them. Now thirteen pegs, with a gap of three. Three, six, nine, twelve, and it keeps going round. This one doesn't close early. It keeps travelling until it has touched every single peg, and it makes a star.

7:31Same idea, completely different picture. Why? Look at the pairs. Twelve pegs and a gap of four. Twelve and four share four. Thirteen pegs and a gap of three. Thirteen and three share nothing but one. They're co-prime. That's the whole difference, and here's why it happens. A shared factor means the thread gets trapped in a smaller loop. Twelve and four share four, so the thread only ever visits every fourth peg, and there are only three of those.

8:06The number of pegs it touches is the total, divided by whatever the pair shares. Twelve divided by four is three. Three pegs. That's our triangle. Thirteen divided by one is thirteen. Every peg. That's our star. So the thread reaches every peg exactly when the pair is co-prime. Here are two more circles, with the gaps left out. See if you can work them out. The first has sixteen pegs, and the thread touches eight of them, all the even ones.

8:42Eight is sixteen divided by two, so the pair must share two. A gap of two does it. The second has twenty-four pegs, and the thread makes a diamond touching only four. Six, twelve, eighteen and twenty-four. Four is twenty-four divided by six, so the pair shares six. A gap of six. Notice we read those off the picture without drawing a single thread. Let's finish by predicting instead of drawing. Four more patterns.

9:16Fifteen pegs, gap of ten. Fifteen and ten share five, so the thread touches fifteen divided by five. Three pegs. A triangle. Ten pegs, gap of seven. Ten and seven share nothing. Co-prime, so every peg. A ten-pointed star. Fourteen pegs, gap of six. They share two, so fourteen divided by two. Seven pegs. Eight pegs, gap of three. Eight and three share nothing. Every peg again. Two of the four reach everything, and both of those are the co-prime pairs.

9:55So here's what co-prime really means. Two numbers with nothing between them. A hiding place no hop can crack. A collision that waits until the very last moment. A thread that refuses to settle until it has touched everything. Three completely different pictures, and underneath all three, the same single fact. Here's my question for you. Pick any number, and ask how many numbers below it are co-prime to it. Try it for twelve, and then for thirteen. Tell me what you notice in the comments.