3
$\begingroup$

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?

Thanks in advance.

  • 0
    @HenningMakholm, I can reproduce the value given with calc 2.2012-12-15

2 Answers 2

5

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.

  • 0
    I have sent a message through the contact page on calc2's site to notify the webmaster.2012-12-15
4

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.

  • 0
    Whoa!. @David this is just awesome!. Thanks for fixing it.2012-12-16