What about the case when you have three modules,

or maybe more modules?

So, for the case of three models,

it turns out that if all pairs (a,b),

(a,c) and (b,c) are coprime,

then remainders modulo a,

b and c uniquely determined remainder modulo their product abc.

And to see that, we can first combine

remainders modulo a and b to get a remainder modulo ab.

Then we can notice that if all pairs are coprime,

then in particular, ab is coprime with c. Why is that?

Well, if a and c are coprime,

then we know that they don't share any prime factors by the unique factorization theorem.

If b and c are coprime,

then b and c don't share any prime factors by unique factorization theorem.

And then if you multiply a and b,

it gets only prime factors from a and from b.

So a and b don't share prime factors with c

so ab also doesn't share any prime factors with c. So,

ab and c are again coprime.

And we can apply the same Chinese remainder theorem for numbers ab and

c. We already get some remainder modulo ab and we need some remainder modulo c,

we just combine them to get a number with some remainder modulo product of a,

b and c which is abc.

So, this not only proves that the remainders modulo

three numbers which are pairwise coprime are independent,

this also gives us a particular algorithm

to build a number with any given remainders modulo a,

b and c. We just successively find, first,

such n modulo first pair,

modulo ab and then we combine ab with c to get n modulo abc.

And if you get even more modules,

we can also go pair by pair.

For example, we have four numbers a, b, c and d,

we first combined a and b and get n modulo ab.

Then we combine ab with c and get n modulo abc.

And then we combine abc with d and get n modulo abcd, and so on.

So it doesn't matter how many modules we have,

if every pair of them is coprime you can

apply Chinese remainder theorem in a few steps and

get any combination of remainders modulo each of these numbers.

Actually, one of the applications of

these Chinese remainder theorem is optimization of computations with very large integers.

So instead of working with large integers themselves,

we can work with their remainders modulo several big prime numbers.

Because, if some very large integers n1 and

n2 are between zero and product of many smaller prime numbers p1,

p2 and up to pk and their remainders modulo each prime number are the same,

then these numbers also have to be the same by the Chinese remainder theorem

because any two different prime numbers are of course coprime.

And if we define two integers which

have equal remainders modulo these set of prime numbers which are coprime,

then their remainders modulo of the product of

these prime numbers also have to be the same by the Chinese remainder theorem.

So the remainder of n1 and n2,

modulo p1, p2 up to pk are equal.

But also both n1 and n2 are themselves less than this product.

So they are themselves these remainders so they have to be equal.

So in this forum, if we represent each integer

n instead of just being this large integer itself,

we can represent it as a set of remainders of the integer modulo p1,

p2 and up to pk which are smaller.

And in this form,

it is fast to sum and multiply

integers because we can just sum and multiply the corresponding remainders modulo p1,

p2 and so on up to pk,

but it is hard to compare which number is bigger.

But if we don't need to compare,

we just need to sum,

multiply and maybe compare for equality,

not for which one is bigger,

than this is actually used in practice to speed up computations.

So, in conclusion, we understand that remainder modulo n uniquely determines

remainder modulo any user of n.

And remainders modulo two different numbers a and b are independent if and only if,

a and b are coprime.

And remainders modulo coprime numbers a and b

uniquely determine the remainder modulo their product.

And we also have an algorithm for constructing

remainder modulo product of numbers given remainders modulo coprime numbers a and b.

And it extends to more modules if every pair of modules is coprime.

And this is one of the crucial building blocks in our future algorithms for cryptography.

And in the next lesson,

we're going to study another operation called Modular exponentiation and its properties.