Chinese Remainder Theorem $\ x\equiv m_k-2\pmod{m_k}$

elementary-number-theory

I am trying to find all integers that give remainders 1,2,3 when divided by 3,4,5 respectively. So I start defining $$a_1=1, a_2=2, a_3=3,$$$$ m_1=3, m_2=4, m_3=5,$$$$ m_1m_2=12, m_1m_3=15, m_2m_3=20,$$$$ m=60$$ All the moduli are pairwise coprime, so by the Euclidean Algorithm $$12x+5y=1\Rightarrow x=-2, y=5.$$ $$15x+4y=1\Rightarrow x=-1, y=4.$$ $$20x+3y=1\Rightarrow x=-1, y=7.$$ Therefor a solution should be $$20\cdot(-2)\cdot1 +15\cdot (-1)\cdot 2+12\cdot (-1)\cdot 3=-40-30-36=-106$$ But under mod 60, this implies a solutions should be of the form, $60t+14$. But it is not. THis is not right. Why did this technique not work?

Solution 1:

Hint $\ 3,4,5\mid x+2\!\!\overset{\rm\color{#90f}U\!\!}\iff \overbrace{{\rm lcm}(3,4,5)}^{\large 60}\mid x+2 \iff {\rm mod}\ 60\!:\,\ x\equiv -2\equiv 58$

where we used $\,\rm\color{#90f}U = $ lcm Universal Property. To find your error(s), check the answer mod $\,3,4,5,\,$ e.g. mod $\,3\!: x \equiv 20(-2)\equiv 2,\,$ not $1$. Looks like you mixed up the inverses in the final formula.

Remark $ $ Above I applied a simple reduction to the constant case optimization of CRT. $ $ If $\,x\equiv a_i\pmod {m_i}$ and $\,\color{#c00}{a_i - m_i = c}\,$ is constant (independent of $i),\,$ the system reduces to a simple constant case of CRT $\,\ x\equiv \color{#c00}{a_i \equiv m_i+c} \equiv c\pmod {m_i}.\,$ Therefore $$ x\equiv c\!\!\!\pmod {m_i}\iff m_i\mid x\!-\!c\!\!\overset{\rm\color{#90f}U\!\!}\iff {\rm lcm}\{m_i\}\mid x\!-\!c\iff x\equiv c\!\!\pmod{{\rm lcm}\{m_i\}}$$ Further examples of this and related optimizations can be found in prior posts.

To help avoid such errors, it might help to understand better the key use of linearity at the heart of the standard Chinese Remainder Theorem [CRT] formula.

$\quad \begin{eqnarray} x\, =\, &a&\!\color{#0a0}{\overbrace{(4\cdot 5\ y_1)}^{\large \equiv\, 1\ ({\rm mod}\ \color{#c00}3)}} \,+\, &b& \overbrace{(\color{#c00}3\cdot 5\ y_2)}^{\large \equiv\, 1\ ({\rm mod}\ 4)}\, +\, &c&\overbrace{(\color{#c00}3\cdot 4\ y_3)}^{\large \equiv\, 1\ ({\rm mod}\ 5)}\quad {\bf [CRT]}\\ \\ \Rightarrow\ \ x\,\equiv\, &a&\ ({\rm mod}\ \color{#c00}3),\ \ x\equiv &b&\ ({\rm mod}\ 4),\ \ x\equiv &c&\ ({\rm mod}\ 5)\\ \end{eqnarray}$

because, $ $ e.g., $\ $ mod $\ \color{#c00}3,\,$ the 2nd and 3rd summands are $\equiv 0,\,$ both having factors of $\,\color{#c00}3.\,$

Hence $\ x\,\equiv\, a\,\color{#0a0}{(4\cdot 5\ y_1)}\equiv a\color{#0a0}{(1)} \equiv a\,\ ({\rm mod}\ 3),\, $ as desired. $ $ Similarly $ $ mod $\,4\,$ and $\,5.$

The key idea is that the braced terms are $\equiv 1$ mod one modulus, and $\equiv 0 $ mod all others. More clearly, if we write the system in vector form $\ x\equiv (a,b,c)\,$ mod $\,(3,4,5)$ then $\rm\,[CRT]$ becomes

$\quad x\, :=\, a\,\color{#0a0}{(1,0,0)} + b\,(0,1,0) + c\,(0,0,1)\equiv (a.b,c)\ $ as desired. $\qquad [\bf Linearity]$

by the green term $\,\color{#0a0}{g \equiv 1}\ ({\rm mod}\ 3),\ \color{#0a0}{g\equiv 0}\ ({\rm mod}\ 4),\ \color{#0a0}{g\equiv 0}\ ({\rm mod}\ 5),\ $ i.e. $\ \color{#0a0}{g\equiv (1,0,0)}\ {\rm mod}\ (3,4,5),\ $ and similarly for $\,(0,1,0)\,$ and $\,(0,0,1).$

Thus once we compute the solutions for the "basis" vectors $(1,0,0),\ (0,1,0),\ (0,0,1)$ we can exploit [Linearity] to generate the general solution as a linear combination of these solutions.

The innate algebraic structure will be clarified if you later study abstract algebra, where you will learn the ring theoretic view of CRT, and vector spaces and modules.

Solution 2:

Another, more direct way of solving this runs as follows. You are looking at $$x \equiv 1 \text{ mod } 3$$ $$x \equiv 2 \text{ mod } 4$$ $$x \equiv 3 \text{ mod } 5.$$ Now put $x=1+3k$ and mod this by $4$. Then $2\equiv 1 +3k \text{ mod } 4$, so $k\equiv -1 \text{ mod } 4$, say $k=4l-1$, hence $x=-2+12l$. Now take the third equation into account. Then $3 = -2+12l\text{ mod } 5$, which is equivalent to $l \equiv 0 \text{ mod } 5$, say $l=5m$. So, finally $x=-2+60m$, whence $x\equiv -2\equiv58 \text{ mod } 60$.