Subject: Re: Chinese remainder theorem
Date: Tue, 2 Sep 1997 00:00:59 -0400
From: Alex Bogomolny
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
- O.Ore, "Number Theory and Its History", or
- 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.