Explore BrainMass

Explore BrainMass

    Chinese Remainder Theorem and Proofs

    This content was COPIED from BrainMass.com - View the original, and get the already-completed solution here!

    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.

    © BrainMass Inc. brainmass.com March 4, 2021, 6:06 pm ad1c9bdddf


    Solution Summary

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