2
$\begingroup$

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.

(I can't post images - please see this link )

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?

$\endgroup$
1
$\begingroup$

You seem to have mixed up the $13$ and the $-6$. It should be:

$$2(41)(-6) + 1(19)(13) \equiv 534 \pmod{779}.$$

$\endgroup$
2
  • $\begingroup$ I see that now, thanks - but then why does my original procedure work for the system in this screenshot? I'm confused what is going wrong... Is there some special case when you have a congruent to 1 (mod n) ? See link here $\endgroup$
    – Kolibrie
    Oct 7 '15 at 0:21
  • 1
    $\begingroup$ @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? $\endgroup$
    – Théophile
    Oct 7 '15 at 16:05

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.