# Chinese remainder theorem when mod divisible with 2

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?

• I think part of the problem may be that gcd(6,10) =/= 1, gcd(10,12) =/= 1, gcd(6,12) =/= 1. Apr 1 '14 at 21:43
• @Bill Dubuque, I don't know what are talking about. I study all answers that I get here. If I didn't thanked you yet for your help and for your time, that don't mean that I "didn't find it helpful" I just need a few more minutes to understand some things there. :) If you can, just make your answer visibile again. I'm sure that will be helpful for me and I hope for other people that have problems with TCR. Apr 1 '14 at 22:28

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$)

• One question: after I substract the second equation from first and I get 4x ≡ - 16 (mod 60) and 5x ≡ (mod 60) is there any reason to continue? I mean, I don't have any chance to obtain b and c zero so all I can do there is to declare that the system has no solution, right? Apr 1 '14 at 23:12
• @redhat: You do have a chance to get $b,c$ zero: in the process of reducing and eliminating the coefficients on $x$, you have a chance for the right hand sides to add up to numbers divisible by $60$, and any such number will simplify to zero.
– user14972
Apr 2 '14 at 0:01

$6,10,12\mid x\!+\!4\iff {\rm lcm}(6,10,12)\mid x\!+\!4\iff 60\mid x\!+\!4\iff x\equiv -4\equiv 56\pmod{60},\$ because $\,{\rm lcm}(6,10,12) = {\rm lcm}(10,12)= 2\,{\rm lcm}(5,6) = 2\cdot 5\cdot 6 = 60.$

Alternatively, using brute-force CRT, 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\,$ $\Rightarrow$ $\, x\equiv -4\equiv 2\pmod 6,\,$ so we are done.

• Thank you for your hint, but I'm stil confuse. Apr 1 '14 at 21:49
• @redhat: Bill figured out the solution by inspection, and was hiding it within a hint. I really don't see how the hint would help a person learn how to solve any similar problem if they weren't able to guess the answer.
– user14972
Apr 1 '14 at 21:52
• @redhat01 Do you know a version of CRT that works for moduli that are not pairwise coprime? Apr 1 '14 at 21:53
• @Hurkyl Not by inspection but, rather, by interpolation. Apr 1 '14 at 21:54
• Of course I don't know, If I knew it I guess I was sleeping right now (is about 1 AM here). :D I see the explanation edited there and now make sense. Thank you :) Apr 1 '14 at 21:59