Drexel dragonThe Math ForumDonate to the Math Forum

Ask Dr. Math - Questions and Answers from our Archives
_____________________________________________
Associated Topics || Dr. Math Home || Search Dr. Math
_____________________________________________

Finding A Number Given Its Divisors and Remainders

Date: 10/22/2003 at 17:22:20
From: Kaytlyn
Subject: complex algebra

Find the smallest whole number that when divided by 5, 7, 9, and 11 
gives remainders of 1, 2, 3, and 4 respectively.  I think there is a 
formula out there, or a way to do it with relationships, but I can't 
figure it out.



Date: 10/22/2003 at 20:20:56
From: Doctor Greenie
Subject: Re: complex algebra

Hi, Kaytlyn -

I don't think there is a formula, but there is a general strategy 
for solving problems like this.

We are looking for a whole number "x" such that

  x/5 leaves remainder 1
  x/7 leaves remainder 2
  x/9 leaves remainder 3
  x/11 leaves remainder 4

What we need to do is change this problem into one where some simple 
expression involving "x" leaves zero remainder when divided by any 
of the numbers 5, 7, 9, or 11; then the problem can be worked as a 
least common multiple problem.  We do this by comparing the divisors 
and the remainders we are given:

For the number "x" which we are looking for, the divisors and 
remainders are

  divisor  remainder
  ------------------
        5    1
        7    2
        9    3
       11    4

When the divisors increase by 2, the remainders increase by 1.  We 
want to find an expression involving x for which the remainders will 
increase by the same amount as the divisors (you will see why 
shortly).  Since the remainders with the number "x" are increasing 
half as fast as the divisors, let's look at the remainders when we 
divide "2x" by these divisors.  Each remainder will simply double. 
For example, if 7/6 has remainder one, then (2*7)/6 = 14/6 has
remainder 2.

So, for the number "2x", the divisors and remainders are

  divisor  remainder
  ------------------
        5    2
        7    4
        9    6
       11    8

The reason we want the remainders to increase at the same rate as 
the divisors is that now we can see that each remainder is 3 less 
than the corresponding divisor.  This tells us that the number "2x +
3" will leave 0 remainder when divided by any of these divisors.

So we are looking for the smallest whole number "x" for which the 
number "2x + 3" is divisible by 5, 7, 9, and 11.  Because these 
divisors are relatively prime, the smallest number divisible by 5, 
7, 9, and 11 (their least common multiple) is

  5*7*9*11 = 3465

And so we have

  2x + 3 = 3465
  2x     = 3462
   x     = 1731

This is the number we are looking for.

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/ 



Date: 10/23/2003 at 22:13:07
From: Kaytlyn
Subject: Thank you (complex algebra)

Thank you so much for helping me.  It's nice to know that if I need
more help I can trust the Dr. Math services.
Associated Topics:
High School Number Theory
High School Puzzles

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

[Privacy Policy] [Terms of Use]

_____________________________________
Math Forum Home || Math Library || Quick Reference || Math Forum Search
_____________________________________

Ask Dr. MathTM
© 1994-2013 The Math Forum
http://mathforum.org/dr.math/