# Mistake in Chinese Remainder Theorem

I made this calculator to solve system of congruences using Chinese Remainder Theorem a while ago and it's always seemed to work for problems I tried, but today I noticed that the solution was wrong.

For $S\equiv1$ (mod 41) and $S\equiv2$ (mod 19),

I consider the system as $S\equiv i$ (mod m) and $S\equiv j$ (mod n),

Then rewrite it as $S\equiv jmy + inx$ (mod m*n), where x and y are found by computing using the Extended Euclidean Algorithm.

So as you see in the link, I finally have $1 = ax + by = 41(-6) + 19(13)$, so then $jmy + inx = 2(41)(13) + 1(19)(-6)$, reducing to 173 (mod 779).

But this answer should be 534. What did I do wrong in my steps?

You seem to have mixed up the $13$ and the $-6$. It should be:
$$2(41)(-6) + 1(19)(13) \equiv 534 \pmod{779}.$$
• @Gage Hmm, that's interesting. It looks like it's a mistake in your code, since in your original example, notice how the $13$ and $-6$ traded places in the two equations in the bottom panel, but not the $41$ and $19$. But in the new screenshot, the $1$ and $-2$ traded places as well as the $11$ and $5$. (It's not clear why you reverse the order of $x$ and $y$; your process would be clearer if you kept them in the same order.) I wonder if your code behaves differently according to whether the Euclidean algorithm takes an even or an odd number of steps? Oct 7 '15 at 16:05