0

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?

redhat01
  • 11
  • 1
  • I think part of the problem may be that gcd(6,10) =/= 1, gcd(10,12) =/= 1, gcd(6,12) =/= 1. – User011123521 Apr 01 '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. – redhat01 Apr 01 '14 at 22:28
  • @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. – Bill Dubuque Apr 01 '14 at 22:46

2 Answers2

0

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

Or the first congruence is redundant by $\,x\equiv 8\pmod{\!12}\Rightarrow x = 8+12j\Rightarrow x\equiv 2\pmod{\!6}.\,$ thus we need only solve the last $2$ congruences. For variety we show how do do this using 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}$

Bill Dubuque
  • 265,059
  • 37
  • 279
  • 908
  • Thank you for your hint, but I'm stil confuse. – redhat01 Apr 01 '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. –  Apr 01 '14 at 21:52
  • @redhat01 Do you know a version of CRT that works for moduli that are not *pairwise coprime*? – Bill Dubuque Apr 01 '14 at 21:53
  • @Hurkyl Not by inspection but, rather, by *interpolation*. – Bill Dubuque Apr 01 '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 :) – redhat01 Apr 01 '14 at 21:59
  • I have a question from using brute-force CRT method. From where is that 8 from "x = 8 + 12j" and what that j means? – redhat01 Apr 01 '14 at 23:17
  • @redhat01 $\, x\equiv 8\pmod{12}\iff 12\mid x-8 \iff x-8 = 12j\,$ for some integer $\,j.\,$ Similarly for the $\,k\,$ introduced modulo $10.\ \ $ – Bill Dubuque Apr 01 '14 at 23:20
  • @redhat $\ \ \ \ x\equiv 8\pmod{12}\iff 12\mid x-8 \iff x-8 = 12j\,$ for some integer $\,j.\,$ Similarly for $\,k\!:\, $ $ 2j\!+\!2\equiv 0\pmod{10}\iff 10\mid 2j\!+\!2\iff 2j\!+\!2= 10k\,$ for some integer $\,k.$ – Bill Dubuque Apr 01 '14 at 23:27
0

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

  • 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? – redhat01 Apr 01 '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. –  Apr 02 '14 at 00:01