Remainder Problem

Date: 10/27/2001 at 10:42:10
From: Virginia K.
Subject: SATI math problem

Hello, Dr. Math!

I'm stuck on a question that was on the SATI math reasoning test some 
time ago. Can you please help me?

Q. There is a number that produces remainder 4 when divided by 5,  
remainder 7 when divided by 9, and remainder 9 when divided by 11.  
Which number is it given that this number is less than 500?

I get intimidated when I get this kind of question with a phrase like 
"less than 500" since that makes me think that I'll have to take into 
account a zillion possibilities. There has to be some easy way, 
doesn't there?

Thank you very much in advance. I always appreciate all the Doctors' 
genuine effort to help everybody!

Date: 10/27/2001 at 11:53:28
From: Doctor Paul
Subject: Re: SATI math problem

The formal way to do this problem is with the "Chinese Remainder 
Theorem."  If you want more information about it, see the Dr. Math 
archives:

   Chinese Remainder Theorem and Modular Arithmetic
   http://mathforum.org/dr.math/problems/donald.07.21.01.html   
  
But I don't think the folks at the SAT expect you to know the CRT and 
in fact, you can solve the problem without knowing the CRT.

Think of what kind of numbers are four more than a multiple of five - 
4, 9, 14, 19, etc.

Do you see that your list will contain every number between 1 and 500 
such that the last digit is either a nine or a four?

Now start making a list of the numbers that are 9 more than a multiple 
of eleven:

  9,  20,  31,  42,  53,  64,  75,  86,  97, 108, 
119, 130, 141, 152, 163, 174, 185, 196, 207, 218, 
229, 240, 251, 262, 273, 284, 295, 306, 317, 328, 
339, 350, 361, 372, 383, 394, 405, 416, 427, 438, 
449, 460, 471, 482, 493

it's easy to add eleven to a number - just increase the units digit by 
one and increase the tens digit by one.

But remember that we're only interested in numbers that end in a 4 or 
a 9.  Do you see that this eliminates a vast majority of the 
possibilities?

The only remaining possibilities are: 

   64, 119, 174, 229, 284, 339, 394, 449

Now one of these must be seven more than a multiple of nine.

But multiples of nine satisfy a unique property - the (repeated, if 
necessary) sum of their digits will always be nine.

For example - in 449, 4+4+9 = 17 and 1+7 = 8, which is not nine, so we 
conclude that 449 is not a multiple of nine. We further conclude 
(rather matter of factly) that 449 must then be 8 more than a multiple 
of nine.

A similar argument shows that for 394, 3+9+4 = 16 and 1+6 = 7, so 394 
is not a multiple of nine and must be seven more than a multiple of 
nine.

So I think the answer you seek is 394.

A final word about the SAT. If I was taking the SAT, I would NEVER go 
through the above method. It would take too long and would mean that I 
was neglecting other problems. The nice thing about the SAT is that 
the answer is sitting right in front of you. There are only 5 choices!  
With a bit of thinking, you should be able to eliminate four of the 
choices in less than 30 seconds.

First of all, if the number doesn't end in a 4 or a 9, it can't be 
four more than a multiple of five so cross it off. If the repeated sum 
of its digits isn't seven, it can't be seven more than a multiple of 
nine, so cross it off. That should leave at most two choices from 
which to choose and I think you can just divide 11 into the number 
easily to see what the remainder is or, if you're running short of 
time, just guess. A 50% chance is pretty good odds as SAT questions 
go.

You often don't need to know how to do the problem to get the right 
answer. All you need to know how to do is eliminate the other 
possibilities.

If you'd like to talk about this some more, please write back.

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