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?

  • $\begingroup$ I think part of the problem may be that gcd(6,10) =/= 1, gcd(10,12) =/= 1, gcd(6,12) =/= 1. $\endgroup$ Apr 1 '14 at 21:43
  • $\begingroup$ @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. $\endgroup$
    – redhat01
    Apr 1 '14 at 22:28
  • $\begingroup$ @redhat01 Oh, I thought you were done and off to sleep since you had already accepted an answer. Please feel welcome to ask questions about my answer if anything is not clear. $\endgroup$ Apr 1 '14 at 22:46

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

  • $\begingroup$ 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? $\endgroup$
    – redhat01
    Apr 1 '14 at 23:12
  • $\begingroup$ @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. $\endgroup$
    – 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.

  • $\begingroup$ Thank you for your hint, but I'm stil confuse. $\endgroup$
    – redhat01
    Apr 1 '14 at 21:49
  • $\begingroup$ @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. $\endgroup$
    – user14972
    Apr 1 '14 at 21:52
  • $\begingroup$ @redhat01 Do you know a version of CRT that works for moduli that are not pairwise coprime? $\endgroup$ Apr 1 '14 at 21:53
  • $\begingroup$ @Hurkyl Not by inspection but, rather, by interpolation. $\endgroup$ Apr 1 '14 at 21:54
  • $\begingroup$ 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 :) $\endgroup$
    – redhat01
    Apr 1 '14 at 21:59

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.