Subject: Re: Chinese remainder theorem
Date: Tue, 2 Sep 1997 00:00:59 -0400
From: Alex Bogomolny

Dear Tan:

Yours is an example of problems solved in general case by what's known as the Chinese Remainder Theorem. You can look it up in

  1. O.Ore, "Number Theory and Its History", or
  2. H.Davenport, "The Higher Arithmetic"

Both available through my bookstore.

In your particular case, you are looking for a number X such that

X = 1 (mod 2,3,4) and X = 0 (mod 5)

which means that divided by 2,3,4 X has the remainder 1 while divided by 5 the remainder is 0.

The first three condition say that (X - 1) is divided by 2,3 and 4, i.e., by their least common multiple which is 12. Therefore, X - 1 = 12t for some integer t.

From X = 0 (mod 5) it follows that X - 1 = 4 (mod 5). Or 12t = 4(mod 5), 3t = 1 (mod 5). As you can check then, t = 5k + 2 for an integer k. Combining this with X = 12t + 1 we get X = 60k + 25.

There are three numbers below 200 in this form: 25, 85 and 145.

Best regards,
Alexander Bogomolny

|Reply|

Copyright © 1996-2017 Alexander Bogomolny

 61229243

Search by google: