# Chinese Remainder Theorem result varies

Sorry if this question is lame. First post!

I was going through this book

Abstract Algebra Theory and Applications Thomas W. Judson Stephen F. Austin State University

In the Chapter 16. Ring Theory the author explains about how Chinese Remainder Theorem can be used to schedule work to Multi-Processor systems in case of Large Integer Calculations.

In a particular example of calculating 2134*1531. He broke it down to this:

x≡ 9 (mod 95)
x≡ 0 (mod 97)
x≡ 30 (mod 98)
x≡ 55 (mod 99)

The result should be 3,267,154. I used two online calculators Calc 1 and Calc 2 and to solve this. Both are giving different and wrong answers 2774788984 and 111543404 respectively. Is there a short and easy way to calculate this?. What is wrong with those calculators?

-
Are you sure these different answers are not all congruent modulo $95\cdot97\cdot98\cdot99$? – Henning Makholm Dec 15 '12 at 23:08
@HenningMakholm has hit the nail on the head. I just checked the first one, but it is indeed giving a value larger than $95\cdot 97\cdot 99\cdot 99$ and congruent to $3267154$. It's not clear why that calculator doesn't reduce the result. – Peter Taylor Dec 15 '12 at 23:09
$11154340 \bmod 98$ is $0$, not $30$. Did you mistype the input, perhaps? – Henning Makholm Dec 15 '12 at 23:11
@HenningMakholm,Peter Yeah, looks like the first calculator has some problems. – nouveau Dec 15 '12 at 23:14
@HenningMakholm, 2134 ≡ 76 (mod 98), 1531 ≡ 61 (mod 98), So: 2134 · 1531 ≡ 76 · 61 ≡ 30 (mod 98) 111543404 is not the right result. – nouveau Dec 15 '12 at 23:17

The problem with calc1 is simply that it doesn't reduce the result modulo the product $95 \cdot 97 \cdot 98 \cdot 99$

The problem with calc2 isn't mathematical at all. It uses a couple of regexes to parse the input, and the second one is buggy: /=([0-9])*mod/ rather than /=([0-9]*)mod/. This means that it loses all but the last character of the given number, so it reduces the last two congruences to $x \equiv 0 \pmod{98}$ and $x \equiv 5 \pmod{99}$

Edit: David Wees has now fixed the regex bug (that was fast!) and calc2 now gives 2685385054 which is congruent to the expected answer.

-
I have sent a message through the contact page on calc2's site to notify the webmaster. – Peter Taylor Dec 15 '12 at 23:41
Thanks a lot @Peter – nouveau Dec 16 '12 at 6:15

I've modified the calculator as described. It does look like a bug. I guess I only tested it with single digit numbers, which does seem a bit dumb... mind you I haven't really looked at it since I coded it a few years ago. So to answer your question, the problem with the calculators is that they have a bug in them as described by the comment above and the creators of the calculators have probably moved onto other projects.

Thanks for letting me know about the fix.

-
Whoa!. @David this is just awesome!. Thanks for fixing it. – nouveau Dec 16 '12 at 6:09