Find Number Given Divisor and Remainder Information

Date: 01/21/2009 at 00:06:19
From: Mark
Subject: Problem solving

A four digit number N leaves remainder 10 when divided by 21, 
remainder 11 when divided by 23 and remainder 12 when divided by 25. 
What is the sum of the digits of N?  The given possible answers are 7,
13, 16, 19 and 22.

I began with 7 and tried to make possible combinations like 1, 6; 2,5;
3,4.  With 1 and 6 the four digit number combinations could be 1006,
6001, 1060, 1600, etc.  Thus there are innumerable possible
combinations, and it will take a long time to try them all.

Is there a faster way to solve a problem like this?

Date: 01/21/2009 at 01:24:04
From: Doctor Greenie
Subject: Re: Problem solving

Hi, Mark -

Working backwards from the given answer choices does indeed give far 
too many possibilities to be practical....

There are formal mathematical methods for solving general problems 
like this (certain remainders with certain divisors); but I have only 
passing knowledge of them.  But often problems like this contain 
patterns that make it relatively easy to solve the problem.

Your example is such a problem.  The divisors and the remainders we 
get when we divide our number N are

  divisor  remainder (when dividing "N")
  ------------------
     21      10
     23      11
     25      12

The divisors increase by 2 from one to the next; and the remainders 
increase by 1.  So let's double our number N and see what happens 
when we divide 2N by these same divisors:

  divisor  remainder (when dividing "2N")
  ------------------
     21      20
     23      22
     25      24

Now the remainder in every case is 1 less than the divisor.  But that 
means the number 2N+1 is evenly divisible by 21, 23, and 25.  These 
divisors have no common factors; so we must have

  2N+1 = 21*23*25

This easily leads us to the answer to the question.

I hope this helps.  Please write back if you have any further 
questions about any of this.

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