# Problem understanding a version of the Chinese Remainder Theorem proof

I have some trouble understanding this particular proof of the Chinese Remainder Theorem.

EDIT:

As far as I understood, this is how the proof goes:

Let $$M_i$$ be the integer we obtain after dividing the product of modules $$M$$ by one of those moduli, as follows $$M_i = M/m_i$$. Then we have $$\gcd(M_i, m_i) = 1$$ , because every factor $$m_r$$ of $$M$$ (where $$r \neq i$$) is coprime to all other factors of $$M$$ and therefore also to $$m_i$$. This is equivalent to saying that $$M_i \equiv_{m_i} 1$$.

This means that there exists a unique integer $$N_i$$, which satisfies $$M_i N_i \equiv_{m_i} 1$$ , which means that $$N_i$$ is the inverse of $$M_i$$ modulo $$m_i$$. At the same time, we know that every other factor $$m_r$$ of $$M$$ (where $$r \neq i$$) divides $$M_i$$, which means $$M_i \equiv_{m_r} 0$$. This means that it also divides $$M_i N_i$$ and $$a_i M_i N_i$$, since if it divides $$M_i$$ it must also divide every multiple of it (is this true or does it follow that it must also divide the inverse of $$M_i$$ ?), i.e. $$a_i M_i N_i \equiv_{m_r} 0$$.

Now as far as I understood from the answers below, if we build the sum $$\sum_{i = 1}^k a_i M_i N_i$$ and take for every summand the remainder modulo $$m_r$$, where $$r \neq i$$, then we will get $$a_i M_i N_i \equiv_{m_r} 0 \$$ for every summand except the one where $$r = i$$, which will then be $$a_r M_r N_r \equiv_{m_r} a_r$$, because $$M_r N_r \equiv_{m_r} 1$$ and if we multiply that with $$a_r$$ we get $$a_r$$ as a remainder (does this $$a_r$$ refer to the ones in the system of congruence equations? i.e. $$x \equiv_{m_r} a_r$$ ? But if that is true, why can't we just use the ones from the system of congruence equations directly?). Therefore, the entire sum $$\bigg( \sum_{i = 1}^k a_i M_i N_i \bigg) \equiv_{m_r} a_r$$ (and not every summand) (does this also mean that if we take a different $$r$$ we obtain a different $$a_r$$ every time?).

Therefore, the solution is $$x = R_M \bigg( \sum_{i = 1}^k a_i M_i N_i \bigg)$$ (how do we get to that? Where does it follow from? And can't we just add the list $$a_1, a_2, ..., a_k$$ instead of computing the sum?)

And the uniqueness part I don't understand at all.

Thank you for the clarifications.

• See here for some intuition on the CRT formula (which - as in your text - is often omitted). Jul 29, 2019 at 15:18
• @BillDubuque Thank you for this useful post. I read it and it helped me with the intuition. However, I still can't seem to get a grasp on those questions I posted. Could you address them in an answer? Aug 5, 2019 at 13:59

All summands but the $$k$$th one are $$\equiv_{m_k}0$$ because for $$i \neq k$$ we have $$M_iN_i \equiv_{m_k} 0$$. Hence only the $$k$$th term $$a_kM_kN_k$$ is left and since $$M_kN_k \equiv_{m_k} 1$$, the whole sum is $$\equiv_{m_k} a_k$$.
• Is this $a_k$ the same one as the one in the congruence equation $x \equiv_{m_k} a_k$ ? And if yes, can't we just add them all together? Jul 31, 2019 at 13:43
He says $$M_i N_i \equiv_{m_\color{red}k} 0\$$ for $$k\ne i,$$ but $$M_i N_i \equiv_{m_\color{red}i} 1.$$
From this it follows that $$\sum_{i=1}^r a_i M_i N_i \equiv_{m_k} a_k .$$
(All terms in the sum are $$\equiv0$$ except the one when $$i=k$$.)