Associated Topics || Dr. Math Home || Search Dr. Math

### 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/
```
Associated Topics:
High School Number Theory

Search the Dr. Math Library:

 Find items containing (put spaces between keywords):   Click only once for faster results: [ Choose "whole words" when searching for a word like age.] all keywords, in any order at least one, that exact phrase parts of words whole words

Submit your own question to Dr. Math
Math Forum Home || Math Library || Quick Reference || Math Forum Search