# Why is this not working? (Chinese remainder theorem weird result)

Trying to find $x \equiv_{17} -4$, $x \equiv_{23} 3$.

OK, so $x = -4 + 17k$ for some $k$.

$-4 + 17k \equiv_{23} 3$. Since $19$ is the inverse of $17 \pmod {23}$, $k \equiv_{23} (3+4)19 \equiv 133$.

Plugging those in: $x = 13 + 17(133) = 2274$.

Now, $2274 \equiv_{17} -4$, but for $\bmod 23$, I have to make it negative $-2274 \equiv_{23} 3$, otherwise it's $20$.

What did I do wrong?

-
When you change $-4$ in $13$, this also changes the values of $k$ (so the $k$ you computed for $-4$ will not work for $13$). If you take $x = -4 + 17 \times 133$ (or $-4+17 \times 18$), it works. – Joel Cohen Oct 6 '11 at 22:09
Why did you all of a sudden change the $-4$ (third line) to $13$ (fourth line)? – André Nicolas Oct 6 '11 at 22:11

You have defined $k$ by $x=-4+17k$, but later you find $x$ using $x=13+17k$. So of course your $x$ is $17$ bigger than it should be.

You could also have made things simpler for yourself: you have $k\equiv_{23} 133$, and so $k \equiv_{23} 18$. This gives the smaller solution $x=-4+17\cdot18=302$, which is the smallest positive solution.

-
Didn't notice I changed. Thanks. Ugh, you won't believe how much time I wasted trying to find where I had a typo. – iDontKnowBetter Oct 6 '11 at 22:21

HINT $\$ Your inference $\rm\:mod\ 23:\ x\: \equiv\: -4 + 17\ k\: \equiv\: 3\ \Rightarrow\ k\: \equiv\: 133\$ is correct, but your next inference is not; viz. $\rm\ y = x+17 = 13 + 17\ k\: \equiv\: x\pmod{17}\:,\:$ but $\rm\:y = x+17\:\not\equiv\: x\pmod{23}\:.\:$

NOTE $\$ The solution can be more quickly calculated by mental arithmetic as follows

$$\rm\displaystyle\ mod\ 23\!:\ -4 + 17\ k\ \equiv\ 3\ \ \Rightarrow\ \ k\ \equiv\ \frac{7}{17}\ \equiv\: -\frac{7}6\ \equiv\: -1-\frac{1}6\ \equiv\: -1-\frac{24}6\ \equiv\: -5\:$$

Therefore $\rm\ \ x\ \equiv\: -4 +17\ (-5)\: \equiv\: -89\ \equiv\ 302\ \pmod{17\cdot 23}$

-