Explore BrainMass

Chinese Remainder Theorem and Proofs

The Chinese Remainder Theorem (CRT) applies when the moduli ni in the system of equations x≡ a1 (mod n1) ... x≡ ar (mod nr) are pairwise relatively prime. When they are not, solutions x may or may not exist. However, the related homogeneous system (2'), in which all ai=0, always has a solution, namely the trivial solution x = 0. The next question addresses these more general problems.

Prove that the solutions of the homogeneous version of the system of equations above (where ai= 0), are precisely the integer multiples of N= least common multiple (n1,..., nr).
Note: Compare this with the uniqueness statement in the CRT.


Solution Summary

A proof involving the Chinese Remainder Theorem is provided. The solution is detailed and well explained.