[MUSIC] Let's consider several problems in number theory and consider the following problem. Suppose a is not divisible by 2, so a is odd. What possible remainders can a have when we divide it by 4? Okay, so there are four possible remainders for the number when we divide it by 4. The remainder can be 0, it can be 1, it can be 2 and it can be 3. So let's consider these cases and see which of them are possible. Okay, clearly the remainder is 0 is impossible. If the remainder is 0, it means that a is divisible by 4. So it has the form 4 times some integer k. And so a is even. But we know that a is odd, so this case is impossible. Okay, there is one more similar case. Consider the remainder 2. So suppose a has remainder 2 when we divide it by 4. So a has the form 4 x some q + 2. Note that here, a is also even. Note that 4 x q is even, and 2 is also even. So the sum of these numbers is also divisible by 2. So this is also impossible since we know that a is not divisible by 2. There two remainders left, 1 and 3, and they are both possible. So clearly, here are simple examples. a = 1, and then if we try to divide 1 by 4, then clearly the remainder is 1. And a = 3 is another example. If we try to divide 3 by 4, then the remainder will be 3. So the remainders 1 and 3 are possible and the remainders 0 and 2 are impossible. Let's consider the following problem. So suppose we have four integers, a, b, c and d. Can we say that two of them must have a difference that is divisible by 3? Can we say that for any four integers, there are two among them such that their difference is divisible by 3? Okay, let's consider some examples. Let's just pick some numbers and see whether this is true or not. Let's pick number 1, 100, 27 and, for example, 5. Okay, let's look at these numbers. Can we find two of them that has difference that is divisible by 3? And indeed, we can. If we subtract 1 from 100, then we have 99, which is divisible by 3. 99 is 3 times 33. We failed, we tried to find an example and we failed. So probably we should try to show that it is always the case. And indeed, this is true. It turns out that this is always the case. Among any four numbers, there are two such that their difference is divisible by 3. Why is it so? And the crucial idea here is the following. Just note that there are only three possible remainders when we try to divide numbers by 3. The remainders are 0, 1 and 2. And we have four numbers. So note that among these four numbers, at least two must have the same remainder when we try to divide them by 4. And so if we subtract these two numbers as we already observed, their difference is divisible by 3. If two numbers have the same remainder when we try to divide them by 3, then their difference is divisible by 3. So it is always the case. Among any four numbers, there are two such that their difference is divisible by 3. Let's consider our next problem. Consider 3-digit non-negative numbers, and the question is the following. Suppose we are trying to divide them by 101. How many of the numbers will have the remainder 7 if you divide them by 101? And here in this problem, we assume that 1-digit numbers and 2-digit numbers are also 3-digit numbers, they just start with 0. So 3-digit numbers are numbers from 0 to 999. Okay, let's see how many numbers do we have in this problem. Let's look at all numbers that has a remainder 7 when we try to divide them by 101. And all of them has the following form. a = 7 + q x 101. And q here is arbitrary integer number. Okay, let's look at all possible values of q and see whether they fall in our interval, whether the result is between 0 and 999. Note that if q is negative, then a is clearly also negative. So these numbers doesn't fall in our interval. Now the first number that falls in our range is for q = 0, then a = 7 + 0 x 101, which is just 7. So for q = 0, a satisfies our property. Okay, now we have q. The remaining values of q are 1, 2, 3 and so on. And the number a grows when q grows. And the last q such that a is still a 3-digit number, it is not hard to check that this q = 9. Then a = 7 + 9 x 101, which is just 7 + 909, which is 916. The next a will be already greater than 1,000. So this is the last q for which our number falls into this interval. So a falls in our interval, a 3-digit for q from 0 to 9. There are 10 such numbers q. So there are 10 such numbers over a 10 3-digit numbers that give a remainder 7 when we try to divide them by 101. [MUSIC]