[MUSIC] Hi, in this lesson we're going to study Chinese Remainder Theorem. It is called so because the Chinese mathematicians were able to prove this theorem approximately 2,000 years ago. And it is concerned with the remainders, modular different numbers. So first, we are going to study the remainders modulo, some numbers and their properties. When remainder modulo one number defines remainder modulo another number. And when the remainders modulo two numbers a and b are completely independent. And when cannot say anything about one remainder given another one. So first let's look at first few integers and their remainders, mod 4 and 2. If we go from 0 we see that remainder of 0 mod both 4 and 2 is of course 0. For 1, the remainders are both 1. For 2, the remainder mod 4 is 2 and mod 2 is 0. Then we get 3 and 1, then, 0, 0 again, 1, 1, 2, 0, and 3, 1. And from these three rows, we can conclude that probably the remainder, mod 4, completely defines the remainder mod 2. Indeed, if two integers, n1 and n2, have the same remainders mod 4. If n1 = n2 mod 4, then it means that 4, by definition, divides the difference between n1 and n2. And as 2 divides 4, 2 also divides this difference between n1 and n2. And so n1 = n2 mod 2, and so the remainders are also the same. This means that indeed the remainder mod 4 defines remainder mod 2. And in particular, if the remainder mod 4 is equal to 0 or 2, then the remainder mod 2 is equal to 0. And if the remainder mod 4 is 1 or 3, then remainder mod 2 is equal to 1. Now let's consider another example of remainders mod 3 and mod 2. Again, we go from n equals to 0, and the remainders are 0, 0. For one they are both 1, then 2, 0, 0, 1, 1, 0, and 2, 1. And so now, we see no correspondence. Basically n mod 3 doesn't define n mod 2 and more than that, all pairs of remainders are possible. So we can see 0, 0, and 0, 1, 1, 0 and 1, 1, 2, 0, and 2, 1. These are all possible pairs of remainders mod 3 and mod 2. Because there are only three values for remainder mod 3 and two values for remainder mod 2. So one remainder, doesn't give any information about another. So now let's recall the divisibility criteria from one of the first modules of this course. Divisibility by 2 criteria is easy. That the last digit is even, then number is even, otherwise number is odd. Divisibility by 5, the last digit is either 0 or 5, then it is divisible by 5, otherwise it is not. And the last digit is the remainder after division of n by 10. So 10 = 2 * 5 and this is why the divisibility criteria by 2 and 5 are defined by the remainder mod 10. So we get remainder of mod 10, and it defines remainders mod 2 and 5. And in particular, if the remainder of mod 10 is 0, then the remainder mod 2 and 5 are also 0. So this is why the last digit is what is important for divisibility by 2 and 5. And for example, for divisibility by 3 the criterion is completely different. It is about the sum of digits. If the sum of digits is divisible by 3, then the number is divisible by 3, otherwise it is not. And so it is not determined just by the last digit. And actually it is independent of the last digits. So whether we know or we don't know the last digit, which is the remainder of division of n by 10, it doesn't give us any information about divisibility by 3. So what happens in the general case, when one remainder defines another and when it doesn't give any information? So first, we want to prove this general lemma that if n1 and n2 have the same remainders modulo some number b. And a divides b, then n1 and 2 has the same remainders modulo a. In other words, if a divides b then remainder modulo b defines remainder modulo a. And to prove it, first we know that if n1 and 2 have the same remainders mod b and n1 is equal to mod b. And so b divides the difference between n1 and n2. b divides this difference and a divides b, so a divides this difference between n1 and n2. And so a divides n1- n2, it means that n1 = n2 mod a. This is what we wanted to prove. So now let's consider the following problem. If n = 1 module 6, then what can we say about n modulo 4? So, we see that 4 doesn't divide 6, so the remainder module 6 doesn't define 4. But maybe we can set at least something, maybe there is some dependence of remain mod 4 on the remainder mod 6. Indeed, if n is even, then the remainder modulo 6 can only be 0, 2 and 4. You can check it yourself. And so, if n is even, then the remainder modulo 6 cannot be 1, okay? So, if n is odd, then n mod 4 can be either 1 or 3. And so, if n =1, then n is both 1 mod 6 and n is 1 mod 4, so it is possible that n = 1 mod 6 and it has remainder 1 mod 4. And if n = 7, then again n = 1 mod 6 and n = 3 mod 4. So it turns out that n mod 4 can be either 1 or 3 if n mod 6 = 1. So if we know the remainder modulo 6, we can make some conclusion about the remainder modulo 4. But we cannot define it uniquely. We can say this can be either 1 or 3. It definitely cannot be 0 or 2. So there is some information in the remainder modulo 6 about the remainder modulo 4. And again, want to understand what is the dependent? So, the remainders modulo 4 and 6 are dependent. And actually, this is because 2 is their common divisor. And, in general, if there is some d that divides both a and b, then the remainders modulo a and b are dependent because the remainder modulo a defines remainder modulo d. And remainder modulo b also defines remainder modulo d. So they have to correspond to one another. And there is some dependence through the remainder modulo d. And it turns out that if a and b don't have any common divisors, if their greatest common divisor is one, then the remainders modulo a and b are completely independent. And we're going to prove it in the next video and this is what Chinese Remainder Theorem is all about. [MUSIC]