Find the Smallest Number - A Remainder Problem

Date: 09/27/2001 at 16:41:22
From: Bob
Subject: Remainder Problem

I have a question on a math problem that I received in class. I got 
the answer by working in Excel and using a guess and check method. I 
don't like working this way and I was wondering if you could help me 
find some kind of formula to figure this out. The answer I got was 
2519, which I believe to be correct. Here is the problem:

Find the smallest number, M, such that:

M/10 leaves a remainder of 9;
M/9 leaves a remainder of 8;
M/8 leaves a remainder of 7;
M/7 leaves a remainder of 6;
M/6 leaves a remainder of 5;
M/5 leaves a remainder of 4;
M/4 leaves a remainder of 3;
M/3 leaves a remainder of 2;
M/2 leaves a remainder of 1.

I know that it has to be a prime number, and I know that it has to 
end in 9 for the first condition to work. I found what each number 
would need to end with as a decimal to have each remainder, and then 
used 10x-1 to get all numbers ending in 9 and plugged in numbers until 
all 9 of the decimals necessary for the conditions to be true turned 
up. Is this a good way to go? Is there an equation that I could use?

Date: 09/27/2001 at 17:49:06
From: Doctor Douglas
Subject: Re: Remainder Problem

Hi Bob, and thanks for writing.

Your method should work fine, although it's a lot of work. Here's 
another method that, if you study it carefully, leads to the correct 
answer, and shows how all the conditions on M above interrelate:

Consider M+1. M+1 is [the smallest number that is] divisible by 
10,9,8,7,6,5,4,3,2, and 1. Clearly 10! (10 factorial) would satisfy 
all of the divisibility conditions, but there is a smaller number 
since many of the factors are unnecessarily duplicated in 10! What I 
mean is this:

   10! = 
     = 1 x 2 x 3 x 4 x 5 x 6 x 7 x 8 x 9 x 10 
     = 1 x 2 x 3 x (2x2) x 5 x (2x3) x 7 x (2x2x2) x (3x3) x (2x5)

Now focus on the factor (2x3) for 6. Clearly if a number is divisible
by 2 and by 3, it is then divisible by 6, so there is no need to 
duplicate this pair (2x3) of factors more than once in the product for 
M+1. Thus we can reduce this to the following product:

   2 x 2 x 2     (three twos are needed for divide-by-eight,
                   this also handles divide-by-two and divide-by-four)
   x 3 x 3       (two threes are needed for divide-by-nine, and
                    when combined with twos, handles divide-by-six)
   x 5            (this handles div-by-five, div-by-ten)
   x 7            (this handles div-by-seven)

So the product of these numbers is the smallest number for M+1, or
2x2x2x3x3x5x7 = 8x9x35 = 72x35 = 2520.  

It's also nice to check that when we divide M (= 2519) by some other 
number that is "covered" by the factors above, such as 2x2x3 = 12, we
get a remainder of 11. And when we divide it by 3x3x7 = 63, we get a 
remainder of 62. And if we divide by 2x2x3x5x7 = 420, we get a 
remainder of 419. Do you see why?

- Doctor Douglas, The Math Forum
  http://mathforum.org/dr.math/