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&#8801; a1 (mod n1) ... x&#8801; 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
https://brainmass.com/math/discrete-math/chinese-remainder-theorem-and-proofs-28891

#### Solution Summary

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

\$2.49