Wrong applying of simple Chinese Remainder Theorem problem

Question

What am I doing wrong? So for the following equations

$$ \begin{align} (*) \left\{ \begin{array}{l} 2x\equiv 3\pmod 5 \\ 4x\equiv 2\pmod 6 \\ 3x\equiv 2\pmod 7 \end{array} \right. \end{align} $$

and $N =\mathrm{lcm}\langle5,6,7\rangle = 210$, giving $N_1 = \frac{210}{5} = 42, \enspace N_2 = \frac{210}{6} = 35, \enspace N_3 = \frac{210}{7} = 30 $.

$$ \begin{align} 42z_1&\equiv 1\pmod 5\Rightarrow\enspace\enspace\;2z_1\equiv 1\pmod 5\Rightarrow\enspace &&\overline{z_1}=\overline{3}\\ 35z_2&\equiv 1\pmod 6\Rightarrow\enspace-1z_2\equiv 1\pmod 6\Rightarrow\enspace &&\overline{z_2}=\overline{-1}\\ 30z_3&\equiv 1\pmod 7\Rightarrow\enspace\enspace\;2z_3\equiv 1\pmod 7\Rightarrow\enspace &&\overline{z_1}=\overline{4} \end{align} $$

So the solution should be $$ \begin{align} \overline{x} &= \overline{3\times42\times3} + \overline{2\times35\times(-1)}+\overline{2\times30\times4}\\ &= \overline{378-70+240}\\ &= \overline{548}\\ &= \overline{128} \end{align} $$

Which is clearly wrong, so I'm wondering which additional steps I need to take to get to the correct answer.

Thanks in advance.

Answer 1

You seem to have solved $$\left\{\begin{array}{c} x\equiv3 \pmod{5}\\x\equiv 2\pmod{6}\\x\equiv 2 \pmod{7}\end{array}\right.$$ But you need to take into account the coefficients on $x$ in each congruence.

$2x\equiv 3\pmod{5}$ means $x\equiv 4\pmod{5}$

$4x\equiv 2\pmod{6}$ means $x\equiv 2 \mbox{ or } 5 \pmod{6}$

$3x\equiv 2\pmod{7}$ means $x\equiv 3\pmod{7}$

Answer 2

\begin{align} 2x &\equiv 3\pmod 5 \\ 4x &\equiv 2\pmod 6 \\ 3x &\equiv 2\pmod 7 \end{align}

First, you need to solve each congruence for $x$.

\begin{align} 2x &\equiv 3 \pmod 5 \\ x &\equiv 4 \pmod 5 \\ \hline 4x &\equiv 2 \pmod 6 \\ 2x &\equiv 1 \pmod 3 \\ x &\equiv 2 \pmod 3 \\ \hline 3x &\equiv 2 \pmod 7 \\ x &\equiv 3 \pmod 7 \end{align}

Note that the solution set (modulo 6) to $4x \equiv 2 \pmod 6$ is $\{2,5\}$ and that both solutions are included in $x \equiv 2 \pmod 3.$

summarizing, we get

\begin{align} x &\equiv 4 \pmod 5 \\ x &\equiv 2 \pmod 3 \\ x &\equiv 3 \pmod 7 \end{align}

One way to compute the solution is this. \begin{align} x &\equiv 4 \pmod 5 \\ x &= 5A + 4 \\ \hline x &\equiv 2 \pmod 3 \\ 5A+4 &\equiv 2 \pmod 3 \\ 2A &\equiv 1 \pmod 3 \\ A &= 2 + 3B\\ x &= 15B + 14 \\ \hline x &\equiv 3 \pmod 7 \\ 15B + 14 &\equiv 3 \pmod 7 \\ B &\equiv 3 \pmod 7 \\ B &= 7C + 3 \\ x &= 105C + 59 \\ x &\equiv 59 \pmod{105} \end{align}

Your way of solving is this way.

$N =\mathrm{lcm}\{5,3,7\} = 105$.

$N_1 = 3 \cdot 7z_1 = 21z_1,\enspace N_2 = 5 \cdot 7z_2 = 35z_2, \enspace N_3 = 5 \cdot 3z_3 = 15z_3 $.

$21z_1 \equiv 1 \pmod 5 \implies z_1 \equiv 1 \pmod 5 \implies N_1 = 21$

$35z_2 \equiv 1 \pmod 6 \implies z_2 \equiv -1 \pmod 6 \implies N_2 = -35$

$15z_3 \equiv 1 \pmod 7 \implies z_3 \equiv 1 \pmod 7 \implies N_3 = 15$

So the solution is \begin{align} x &\equiv 4 \cdot 21 - 2\cdot 35 + 3 \cdot 15 \pmod{105}\\ x &\equiv 59 \pmod{105} \end{align}