Chinese Remainder Theorem Proof Summation

MrRieding

New member
Joined
Jan 1, 2017
Messages
3
Hello everyone,
In the most popular proof of the Chinese Remainder Theorem, apparently some unique solution "X" is congruent to the sum AiMiYi, where A is some integer, Mi is the product of all "m" divided by mi (Ai mod mi), and Yi is the inverse of Mi, making AiMiYi congruent to Ai mod Mi.

To be clear, I am talking about the summation in this proof: https://brilliant.org/wiki/chinese-remainder-theorem/

I am sorry if this is unclear. My question is, how do we know that this summation produces the solution to the system?

Thanks!
 
Hello everyone,
In the most popular proof of the Chinese Remainder Theorem, apparently some unique solution "X" is congruent to the sum AiMiYi, where A is some integer, Mi is the product of all "m" divided by mi (Ai mod mi), and Yi is the inverse of Mi, making AiMiYi congruent to Ai mod Mi.

To be clear, I am talking about the summation in this proof: https://brilliant.org/wiki/chinese-remainder-theorem/

I am sorry if this is unclear. My question is, how do we know that this summation produces the solution to the system?

Thanks!

Thanks for giving the link to the proof, rather than just describing it.

They tell you exactly why, in the section called "proof"! What part of that don't you understand?

To paraphrase, they say that for each i, (a) x, which is defined as the sum a1y1z1 + a2y2z2 + ... + anynzn, is congruent (mod ni) to the one term aiyizi, since every other term is a multiple of ni, and is therefore congruent to 0. Then (b) this one term is congruent to ai, because zi was chosen as the inverse of yi so that yizi is congruent to 1. And that's what it means to be a solution!

Can you now clarify your difficulty?
 
Top