Chinese Remainder Theorem Proof Summation

[MrRieding]

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!

 

[Dr.Peterson]

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 a₁y₁z₁ + a₂y₂z₂ + ... + a_ny_nz_n, is congruent (mod n_i) to the one term a_iy_iz_i, since every other term is a multiple of n_i, and is therefore congruent to 0. Then (b) this one term is congruent to a_i, because z_i was chosen as the inverse of y_i so that y_iz_i is congruent to 1. And that's what it means to be a solution!

Can you now clarify your difficulty?