Counting Integers: Divisibility and g.c.d.

Transcript

0:00Introduction

Hello everyone! Okay, one small puzzle before we start. Take the numbers from one to five hundred. How many of them share no common factor with thirty, other than one? Will you check all five hundred, one by one? That would take an hour, right? By the end of this video, you will do it in one line, with two tools: a special bracket, and our old friend, inclusion and exclusion. In JEE, counting questions on divisibility come up often. So, let's begin.

0:33Counting multiples with the bracket

So, the first tool. The number of multiples of d among the numbers from one up to N, is N over d, inside square brackets. The three dots just mean all the numbers in between, okay? Let's try it. How many multiples of seven are there from one to one thousand? One thousand over seven is one hundred and forty two point eight, and a bit. But there is no point eight of a multiple, right? So we keep the whole part: one hundred and forty two. That is what square brackets do. Square brackets around x give the greatest integer less than or equal to x, and that little sign means less than or equal to. Got it? Now the numbers run from a up to b. Count the multiples up to b, and throw away those up to a minus one: the greatest integer of b over d, minus the greatest integer of a minus one, over d. Now tell me. Why a minus one, and not just a? Yes, exactly! Because a itself may be a multiple of d, and it belongs to our range. So, the multiples of seven from one hundred to one thousand: one hundred and forty two, minus the greatest integer of ninety nine over seven, which is fourteen. One hundred and twenty eight. That's it!

1:41Coprime to m: remove the multiples of its primes

Alright, the second idea. We say n is coprime to m when the two share no common factor except one. So think. When does n share a factor with m? Exactly when some prime factor of m divides n. Correct! So break m into primes: p one to the power a, times p two to the power b, and so on. The small one and two below each p are just labels, and a and b up top are powers. Then we remove the multiples of p one, of p two, and so on. Okay? So, from N, subtract the multiples of each prime, and we are done, right? Oh no, careful! Some numbers are multiples of p one and p two together, and we removed them twice! Those are exactly the multiples of p one times p two. Clear? So this is inclusion and exclusion again. Start with N, subtract the singles, add back the pairs, subtract the triples, and so on. Each of these counts is just our bracket again. With me? And when N equals m itself, there is a beautiful shortcut. This Greek letter is phi. Phi of m counts the integers from one to m that are coprime to m. Phi of m equals m, times one minus one over p one, times one minus one over p two, and so on. Okay? Take three hundred and sixty: two cubed, times three squared, times five. The dots just mean times. So phi of three sixty is three sixty, times one half, times two thirds, times four fifths: ninety six. See, the powers three and two do not change the fractions at all. Only the primes do. Beautiful, isn't it?

3:20When the g.c.d. is d

Now the third idea: the g c d, the greatest common divisor, okay? If the g c d of n and m is d, then n equals d times k. And once d is taken out, nothing else can be common: the g c d of k and m over d is one. Clear? Let's use it on the numbers n up to one hundred whose g c d with twelve is four. Each is four times k, with k at most twenty five. So, all twenty five multiples of four, right? No, no, wait! Look at twelve, twenty four, thirty six, and so on. They are multiples of four, but their g c d with twelve is twelve, not four. They must go. Got it? Here, m over d is twelve over four, that is three. So the g c d of k and three must be one: k is not a multiple of three. Twenty five, minus the greatest integer of twenty five over three, which is eight: seventeen numbers. That's it!

4:15Example 1: 3-digit numbers divisible by 5 but not by 3

Alright, time for the examples. How many three-digit numbers are divisible by five, but not by three? On the right, circle F holds the multiples of five, and circle T the multiples of three. Pause the video, and try it first. Done? Okay, let's check. Three-digit numbers run from one hundred to nine hundred and ninety nine. The greatest integer of nine nine nine over five is one hundred and ninety nine. With me? Now we remove the ones below one hundred. So we subtract the greatest integer of one hundred over five, that is twenty, right? No, no, wait! One hundred is itself a multiple of five, and it has three digits. Remember, a minus one! Subtract the greatest integer of ninety nine over five, nineteen. One hundred and ninety nine minus nineteen: one hundred and eighty. Okay? Now the middle of the diagram. Which numbers are divisible by both five and three? The multiples of fifteen, yes! Five and three have no common factor. Same method: nine nine nine over fifteen, in brackets, is sixty six, and ninety nine over fifteen is six. Sixty six minus six: sixty, in the middle. Clear? So, divisible by five but not by three is only the F part. One hundred and eighty minus sixty: one hundred and twenty. Perfect!

5:40Example 2: numbers from 1 to 500 coprime to 30

Now, remember our puzzle from the start? Let's finish it. How many of the numbers from one to five hundred are coprime to thirty? Pause and try. Hint: start with the prime factors of thirty. Done? Okay, let's check. Thirty is two times three times five, so we remove the multiples of two, three and five. Okay? First, the singles. Five hundred over two, in brackets, is two hundred and fifty. In the same way, five hundred over three gives one hundred and sixty six, and five hundred over five gives one hundred. So the total is five hundred and sixteen. But five hundred minus five hundred and sixteen is negative! Did we make a mistake? No! Don't panic, just keep going. We removed some numbers twice. So add back the pairs: the multiples of six, ten and fifteen. Eighty three, fifty and thirty three: one hundred and sixty six. Clear? Now the multiples of thirty. They were removed three times, then added back three times, so right now they are not removed at all! Subtract them once: five hundred over thirty, in brackets, is sixteen. Got it? So, five hundred, minus five hundred and sixteen, plus one hundred and sixty six, minus sixteen, equals one hundred and thirty four. One line, and no hour of checking. Puzzle solved! Very good!

6:57Quick revision: multiples, coprime counts and the g.c.d.

So, quick revision. Multiples of d up to N: the greatest integer of N over d. From a to b, subtract the count up to a minus one. Coprime to m: inclusion and exclusion over the primes of m, and when N equals m, use phi of m. And when the g c d of n and m is d, write n as d times k, with k coprime to m over d. Now go and try the practice problems on this page. You will find them easy, I promise. All the best!