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
    Are you sure these different answers are not all congruent modulo $95\cdot97\cdot98\cdot99$?2012-12-15
  • 0
    @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.2012-12-15
  • 0
    $11154340 \bmod 98$ is $0$, not $30$. Did you mistype the input, perhaps?2012-12-15
  • 0
    @HenningMakholm,Peter Yeah, looks like the first calculator has some problems.2012-12-15
  • 0
    @HenningMakholm, 2134 ≡ 76 (mod 98), 1531 ≡ 61 (mod 98), So: 2134 · 1531 ≡ 76 · 61 ≡ 30 (mod 98) 111543404 is not the right result.2012-12-15
  • 0
    @Jay: I wouldn't say it "has problems", since it actually does give a valid solution to the four equations you put in. It's just not the _smallest_ (nonnegative) solution.2012-12-15
  • 0
    @HenningMakholm Ah, yes. You're right.2012-12-15
  • 0
    @Jay, that's what I'm saying -- 111543404 is not the right result, but it does satisfy three of your four equations and is only a single missed keypress from satisfying the last one. I'm suggesting that you mistyped the input to calc-2 as `x=0 mod 98` instead of `x=30 mod 98`.2012-12-15
  • 0
    @HenningMakholm I rechecked. My input is correct. It's giving the same result for both `x≡0 mod 98` as well as `x≡30 mod 98`2012-12-15
  • 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