1
$\begingroup$

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?

$\endgroup$
2
  • $\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
    Commented Mar 30, 2017 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
    Commented Mar 30, 2017 at 20:30

1 Answer 1

Reset to default
1
$\begingroup$

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.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .