# CRT- finding the value of number from it's tuple representation.

In Chinese Remainder Theorem(CRT): If $$A\ \ \mathcal{E}\ Z_m$$, and $$a_i = A mod\ m_i$$, where,

$$M = \prod^k_{i=1} \ m_i$$, and $$m_i$$ are pairwise relatively prime.

Now, if M is great, it(is said in the text) can be dealt with by treating it as a k tuple entity , i.e. $$A \leftrightarrow (Amod\ m_1, Amod\ m_2, ... , Amod\ m_k)$$ $$\Rightarrow A \leftrightarrow (a_1, a_2, ..., a_k)$$

**Now the problem is with the explanation given to obtain A back from the tuple, **, the explanation goes as follows:

Let, $$M_i = M/m_i$$ for $$1 \leq i \leq k$$. Here, $$M_i = m_1\times m_2\times ...\times m_{i-1}\times m_{i+1}\times ...\times m_k$$, $$M_i \equiv 0 mod \ m_j \forall i\neq j$$. So far so good

Now, let, $$ci = M_i \times (M^{-1}_1 mod\ m_i) \ \ \ \#\#PTN1$$

and, directly, it's given: $$A \equiv \sum ^k_{i=1}a_ic_i (mod M) \ \ \ \#\#PTN2$$

In PTN1:
Why is this variable defined, no reason is mentioned, it looks a bit arbitrary, and isn't the value of $$c_i$$ always 1 in mod $$m_i$$?

In PTN2:
I typically don't understand how is this equation giving us the value of A back to us? There certainly isn't a clear explanation.

Besides, chinese remainder theorem, I don't know if there are different versions of it, but googling the solution was hard , as this particular explanation is different from others that present it as a way to solve linear congruencies.

• It's defined so that $\ c_i \leftrightarrow (0,0,\ldots 1,\ldots, 0)\,$ is the "basis" vector with $1$ in the $i$'the coordinate. Then $(a_1,\ldots,a_n) = a_1 c_1 + \ldots + a_n c_n\,$ yields the general solution. See this answer for details. – Bill Dubuque Apr 29 at 17:04