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/
Search the Dr. Math Library:
Ask Dr. MathTM
© 1994- The Math Forum at NCTM. All rights reserved.