0
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – Bill Dubuque Apr 29 at 17:04

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.