Chinese remainder theorem

Statement

Chinese remainder theorem

Let be positive non-zero, non-unit elements for where are pairwise coprime and set . Then for any with and there exists a unique where such that

Proof

Existence

We proceed by induction.

If then from the extended Euclidean algorithm we could construct and such that .

Note this gives (mod and (mod ).

Then consider similarly Suppose we have now solved it for with .

Note that first we can solve the case with 2 variables for and . So we get an such that Now solve the problem using the induction assumption with for and with for and . Giving where which by construction gives Thus by induction we have show existence.

Uniqueness

Suppose were two such solutions then for all .

As the are coprime we have that .

As the only possible solution is and we have uniqueness.