Chinese remainder theorem, noncoprime moduli $6,10,12$

Question

I can't understand how chinese remainder theorem works when the all 3 mod numbers are divisible with 2. For example:

x = 2 mod 6
x = 6 mod 10
x = 8 mod 12

* = means congruent

And I do:

n = 6 * 10 * 12 = 720
c1 = 720/6 = 120
c2 = 72
c3 = 60

Until here all is clear, but now when I do: 120x = 2 mod 6 => x = (120 * ?) / 6 = something and remainder 2 I really can't find that number. What I'm doing wrong?

Answer 1

I don't follow how you're organizing your work.

The Chinese Remainder Theorem says the combined modulus is the least common multiple, not the product. In this case, the combined modulus is $60$. This makes things trickier.

You could work a pair of moduli at a time: if you have two equations

$$ x = ga \pmod {gm} \qquad x = gb \pmod {gn} $$

then by reducing modulo $g$, you know $x \equiv 0 \pmod{g}$. If you set $x = gx'$, then you can divide out the $g$'s from everything to get

$$ x' = a \pmod{m} \qquad x' = b \pmod{n} $$

and can work from there. Sometimes this method requires a change of variable first: e.g. maybe it's $x+1 \equiv ga$ and $x + 1 \equiv gb$.

---

IMO it's more straightforward to multiply each equation to get a common modulus:

$$ \begin{align} 10x &\equiv 20 \pmod{60} \\ 6x &\equiv 36 \pmod{60} \\5x &\equiv 40 \pmod{60} \end{align}$$

then you can use a variation of the Euclidean algorithm to simplify the system: e.g. we can subtract the second equation from the first to reduce it to $4x \equiv -16 \pmod{60}$, and so forth. Eventually, you'll be left with three equations:

$$ x \equiv a \pmod{60} \qquad 0 \equiv b \pmod{60} \qquad 0 \equiv c \pmod{60} $$

if $b\equiv c\equiv0 \pmod{60}$, then $x \equiv a \pmod{60}$ is the solution to your system. If $b$ or $c$ is nonzero modulo $60$, then the system has no solutions.

(the leading coefficient on $x$ in the last set of equations is $1$ because $\gcd(10,6,5) = 1$)

Answer 2

The first congruence is redundant: $\,x\equiv 8\pmod{\!12}\,\Rightarrow\,$ $ x = 8+12j\,\Rightarrow\, x\equiv 2\pmod{\!6},\,$ so only the last $2$ congruences matter: $\,x\equiv -4 \pmod{\!10\ \&\ 12}\!\iff$ $\,x\equiv -4\pmod {\!\color{#0a0}{60}}$, by CCRT and $\,{\rm lcm}(10,12)= 2\,{\rm lcm}(5,6) = 2\cdot 5\cdot 6 = \color{#0a0}{60}.$

---

Alternatively, apply Easy CRT, i.e. the last congruence holds $\iff x = 8\! +\! 12j,\,$ hence ${\rm mod}\ 10\!:\,\ 6 \equiv x = 8\!+\!12\color{#c00}j \iff 2j\equiv -2\iff 2j= -2\!+\!10k\iff \color{#c00}{j=-1\!+\!5k},\,$ thus we have that $\,x = 8\!+\!12(\color{#c00}{-1\!+\!5k}) = -4\!+\!60k$.

---

Or we can apply the fractional extended Euclidean algorithm.

$\begin{align} x&\equiv 6\!\!\!\pmod{\!10}\\ x&\equiv 8\!\!\!\pmod{\!12}\end{align}$ $\iff \begin{align} 6x&\equiv 36\!\!\!\pmod{\!60}\\ 5x&\equiv 40\!\!\!\pmod{\!60}\end{align}$

${\rm mod}\,\ 60\!:\,\ x\equiv \dfrac{36}{6} \overset{\large\frown}\equiv \dfrac{40}{\color{#90f}{5}} \overset{\large\frown}\equiv \dfrac{\color{#c00}{-4}}{\color{#0a0}{1}} $

$\!\begin{array}{rrl} \text{or, equationally:} \ \ [\![1]\!]\!:\!\!\!& 6\,x\!\!\!&\equiv\ \ 36\\ [\![2]\!]\!:\!\!\!& \color{#90f}{5}\,x\!\!\!&\equiv\ \ 40\\ [\![1]\!]-[\![2]\!]=:[\![3]\!]\!:\!\!\!& \color{#0a0}{1}\,x\!\!\!&\equiv \color{#c00}{-4} \end{array}$