Chinese remainder theorem
The Chinese remainder theorem is a mathematical result about modular arithmetic. It describes the solutions to a system of linear congruences with distinct moduli. As well as being a fundamental tool in number theory, the Chinese remainder theorem forms the theoretical basis of algorithms for storing integers and in cryptography. The Chinese remainder theorem can be generalized to a statement about commutative rings; for more about this, see the "Advanced" subpage.
The Chinese remainder theorem:
has solutions, and any two solutions differ by a multiple of .
Methods of proof
The Theorem for a system of t congruences to coprime moduli can be proved by mathematical induction on t, using the theorem when both as the base case and the induction step. We mention two proofs of this case.
As usual we let denote the set of integers modulo n. Suppose that are coprime. We consider the map f defined by
We claim that this map is injective: that is, if then or . Suppose that or . Then each of and divides : but since and are coprime, it follows that their product divides also.
But the two sets in question, the first consisting of all residue classes modulo and the second consisting of pairs of residue classes modulo and , have the same number of elements, namely . So if the map f is injective, it must also be surjective: that is, for every possible pair , there is an mapping to that pair.
The existence proof assures us that the solution exists but does not help us to find it. We can do this by appealing to the Euclidean algorithm. If and are coprime, then there exist integers and such that
and these can be computed by the extended Euclidean algorithm. We now observe that putting