In the following system of congruences, $n_1$ and $n_2$ are relatively prime.

\begin{align} \newcommand{\mod}{\text{mod }} a &\equiv a_1 \; (\mod n_1) \\ a &\equiv a_2 \; (\mod n_2) \\ \end{align}

Using the Chinese Remainder System described in [CLRS: Introduction to Algorithms (Theorem 31.27, Page 951, the 3rd edition)], we have

$$m_1 = n_2, m_2 = n_1$$ \begin{align} c_1 = m_1(m_1^{-1} \;\mod n_1) = n_2 (n_2^{-1} \;\mod n_1) \\ c_2 = m_2(m_2^{-1} \;\mod n_2) = n_1 (n_1^{-1} \;\mod n_2) \end{align}

Then, we have ($n = n_1 n_2$ in the following)

\begin{align} a &= (a_1 c_1 + a_2 c_2) \; (\mod n) \\ &= \left(a_1 n_2 (n_2^{-1} \;\mod n_1) + a_2 n_1 (n_1^{-1} \;\mod n_2)\right) \; (\mod n) \end{align}

Another method is to solve the congruences directly as follows.

$$a \equiv a_1 \; (\mod n_1) \Rightarrow \exists x \in \mathbb{Z}, a = n_1 x + a_1$$

Substitute $a$ into the second congruence, we get $$n_1 x \equiv a_2 - a_1 \; (\mod n_2)$$

Solving the congruence above, we get $$x = (a_2 - a_1) (n_1^{-1} \; \mod n_2)$$

Therefore, \begin{align} a &= n_1 x + a_1 \\ &= n_1 \left( (a_2 - a_1) (n_1^{-1} \; \mod n_2) \right) + a_1 \\ &= a_2 n_1 (n_1^{-1} \;\mod n_2) - a_1 n_1 (n_1^{-1} \;\mod n_2) + a_1 \end{align}

However, the result is not the same as the one obtained by applying the Chinese Remainder Theorem. What is wrong with it?

  • $\begingroup$ Maybe the expressions are both correct (although they appear quite different)! If I did not make an error in the calculation, both solutions seem to satisfy the required congruences. Note that the expressions only have to be congruent modulo $n$ $\endgroup$ – Peter Mar 30 '17 at 16:02
  • $\begingroup$ Really, how do you know they are not the same? $2+2$ and $12\over3$ look different as well, but there is a catch. $\endgroup$ – Ivan Neretin Mar 30 '17 at 20:30

Hint $\ {\rm mod}\ (n_1,n_2)\!:\!\!\! \underbrace{(\color{#0a0}{a_1,0})\,+\,(0,a_2)} _{\Large \begin{array}{r} \color{#0a0}{n_2(n_2^{-1}a_1\bmod n_1})\\ +\ n_1(n_1^{-1}a_2\bmod n_2) \end{array} }\, \!\!\!\!\!\!\!\!\equiv\, (a_1,a_2)\, \equiv\,\underbrace{(\color{#c00}{a_1,a_1})\, +\, (0,\,a_2-a_1)}_{\Large \color{#c00}{a_1} +\: n_1(n_1^{-1}(a_2-a_1)\bmod n_2)\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\! }$

i.e. $\ \color{#0a0}{n_2(n_2^{-1}a_1\bmod n_1) \equiv a_1}\!\pmod {\!n_1}\,$ and $\equiv \color{#0a0}0\pmod {\!n_2},\,$ i.e. it's $\equiv\color{#0a0}{(a_1,0)}\pmod{\!n_1,n_2}$

Remark $\ $ These "vector" operations will be arithmetically clarified when one learns about the ring-theoretic view of CRT = Chinese Remainder Theorem.

| cite | improve this answer | |

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.