Hi. In this video,

we're going to prove Chinese Remainder Theorem about

the dependence between remainders modular coprime numbers a and b,

and we'll give a constructive proof which will, in turn,

give us an algorithm to use this theorem in practice to build

some numbers with given remainders modulo a and b if we want them.

So the theorem itself states that if a and b are coprime,

then for any remainder r_a modulo a and any remainder r_b modulo b,

there exists some integer n such that n has

remainder r_a modulo a and remainder r_b modulo b.

Also, it says that if there are two such integers n1 and n2,

then their remainders, modulo product of a and b, are the same.

So in other words,

we can consider all ab possible remainders modulo of the product of a and b 0,

1, 2, and so on up to ab minus one.

Every such remainder corresponds to a pair of remainders r_a and r_b.

r_a is the remainder of r modulo a and r_b is the remainder of r modulo b.

So we claim that if you can see their pairs

corresponding to each such r from zero to ab minus one,

then each of the possible ab pairs r_a,

r_b appears there exactly once,

corresponds to some remainder r. So let's prove the first part that

if n1 and n2 correspond to the same pair of

remainders then their remainders modulo ab are the same.

This is the easier part.

First, we know that n1 and n2 both have remainder r_a modulo a,

and from this it follows that n1 is equal to n2

modulo a so a divides the difference between n1 and n2.

Similarly, we can conclude that b divides the difference between n1 and n2.

And also we know that a and b are coprime

and from the theorem we proved in the previous lesson,

we know that if two coprime numbers divides some number,

then their product divides the same number.

So ab divides difference n1 minus n2.

And this means, in turn,

that n1 is equal to n2 modulo ab.

So indeed, the remainders of n1 and n2 modulo ab are the same.

So we proved the second part of the theorem that actually means

that different remainders modulo ab lead to different pairs r_a,

r_b and this already actually proves the first part of the theorem.

Indeed the number of remainders r modulo ab is ab,

all the numbers from 0 to ab minus one,

and the number of possible pairs of remainders r_a,

r_b is also a times b because there are a possible remainders

modulo a and b possible remainders modulo b and all pairs of them are possible.

So each r corresponds to unique pair r_a, r_b.

We just proved it because if two numbers have the same pair of remainders r_a,

r_b then their remainders modulo ab are the same.

So if two numbers between zero and ab minus

one have the same pair of remainders modulo a and b,

they have to coincide.

So each r between zero and ab minus one,

which is a remainder modular ab,

actually corresponds to unique pair,

and the number of pairs is equal to the number of remainder.

So each pair also corresponds to unique r.

For each pair there has to be some remainder r that corresponds to it.

Otherwise, the quantities don't come out equal.

So we will also show a constructive proof.

This proof just says that okay, for any r_a,

r_b there is some remainder r which corresponds to this pair but we don't

know how to find it and we want

some algorithm that will find it for us to use in applications.

So again, the greatest common divisor of a and b is equal to one.

And so it follows from

the extended Euclid's algorithm from the previous model that one can be

represented as sum of a times x plus b times y for some integer x and y.

From this, it follows that ax is equal to one modulo b

and by is equal to one modulo a from this equality.

So these two equalities already give us some pairs of remainders.

In particular, ax corresponds to pair of remainders 0 and 1

because a divides ax so remainder of ax modulo a is 0,

and remainder of ax modulo b is one because ax is equal to one modulo b.

Similarly, by corresponds to the pair 1, 0.

So we have pairs 0,

1 and 1, 0.

And from those pairs,

we can combine to get any pair we want.

If you want pair r_a,

r_b then we can just combine pair 1,

0 with co-efficient r_a with pair 0,

1 with coefficient r_b and sum them up and you'll get exactly pair r_a and r_b.

Let's check that. So consider n which is equal to

r_a times by because by corresponds to pair 1,

0 plus r_b times pair ax because ax corresponds to 0, 1.

So consider such n. And first let's see what is the remainder of this n modulo a.

So n is the sum of two numbers and the second number,

r_b times a times x is divisible by a.

So it is equal to zero modulo a.

So we only need to look at the remainder of r_a times b times y modulo a.

And also we know that by is equal to one modulo a.

So we can just cancel the terms b and y and only r_a remains.

So n is indeed equal to r_a modulo a.

Now, let's consider n modulo b and similarly the first sum

in the sum of these two terms r_a times b times

y is divisible by b so it is equal to zero modulo b,

and then r_b times a time x is equal to r b because a times x is equal to

one modulo b so we can just cancel ax and only r_b returns.

So indeed these particular n has pair of remainders r_a,

r_b corresponding to modulo a and modulo b.

And this gives us an algorithm to build

integer n with the given pair of remainders modulo a and modulo b.

The algorithm is the following.

We take numbers a and b and we launch the extended Euclid's algorithm to

represent their common divisor one as the sum of ax and by for some integers x and y.

And now we know these x and y.

And then to compute n which has remainders r_a and r_b modulo a and b correspondingly,

we just compute r_a times by plus r_b times ax and we get the n we need.

So, this is our algorithm again.