Remainders of 1, 2, 3, 4

Date: 10/09/2001 at 14:10:43
From: Laura 
Subject: Can Do puzzle question

Find the smallest whole number that when divided by 5, 7, 9, and 11 
gives remainders of 1, 2, 3, and 4 respectively. 

Show all work. This involves more than just writing the answer down 
and dividing.

Date: 10/09/2001 at 16:42:28
From: Doctor Jodi
Subject: Re: Can Do puzzle question

Hi Laura,

Thanks for writing us. There's a similar problem answered at

   Find the Smallest Number - A Remainder Problem
   http://www.mathforum.org/dr.math/problems/bob.09.27.01.html   

Take a look and write back if you have more questions or want to 
discuss your problem some more.

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

Date: 10/09/2001 at 16:48:37
From: Doctor Greenie
Subject: Re: Can Do puzzle question

Hello, Laura -

The first kind of problem like this typically asks something like 
"what is the smallest whole number that is divisible by 2, 3, 4, ..., 
and 9?"  For a problem like this, you probably know that you build the 
answer using the prime factorizations of all the divisors.

The first extension of this type of problem is one that asks something 
like "what is the smallest whole number that leaves a remainder of 1 
when divided by 2, 3, 4, 5, or 6?"  Using the modulo notation (with 
"=" being the modulus symbol, since I don't have a "three-bar equals 
sign" on my keyboard), the information here tells us that, for the 
number x we are looking for...

    x = 1 mod 2
    x = 1 mod 3
    x = 1 mod 4
    x = 1 mod 5
    x = 1 mod 6

We can re-write this information as

    x-1 = 0 mod 2
    x-1 = 0 mod 3
    x-1 = 0 mod 4
    x-1 = 0 mod 5
    x-1 = 0 mod 6

When we do this, the problem becomes similar to the previous one, 
except that now "x-1" is the number n which is divisible by 2, 3, 4, 
5, and 6, so the answer to the problem is one more than that number n.

Another level of difficulty is introduced into this type of problem 
when the problem asks something like "what is the smallest whole 
number that leaves remainders of 3, 4, 5, and 6, respectively, when 
divided by 5, 6, 7, and 8?" 

Here we have the following information, in modulo notation, about our 
number x:

    x = 3 mod 5
    x = 4 mod 6
    x = 5 mod 7
    x = 6 mod 8

We notice here that the remainders are always 2 less than the divisor; 
another way of expressing this is that the difference between 
successive divisors is the same as the difference between successive 
remainders. Because the difference between successive divisors is the 
same as the difference between successive remainders, we can solve 
this type of problem by rewriting the given information as

    x+2 = 5 = 0 mod 5
    x+2 = 6 = 0 mod 6
    x+2 = 7 = 0 mod 7
    x+2 = 8 = 0 mod 8

So we see that here we look for the smallest whole number n that is 
divisible by 5, 6, 7, and 8; and the answer to the problem is 2 less 
than the number n.

In your problem, yet another element has been added to change the 
required method of solution. The given information in your problem is 
the following:

    x = 1 mod 5
    x = 2 mod 7
    x = 3 mod 9
    x = 4 mod 11

Here, the remainder only increases by 1 each time the divisor 
increases by 2. We would like to find a way to re-write this 
information in such a way that the remainder increases by 2 each time 
the divisor increases by 2 - so that the problem looks like the 
preceding one. We can do this by getting really clever here and 
rewriting the given information as follows:

    2x = 2 mod 5
    2x = 4 mod 7
    2x = 6 mod 9
    2x = 8 mod 11

The idea here is actually quite simple: we had the information that, 
for the number x we are looking for, the remainders increased by 1 
each time the divisor increased by 1; by doubling our number to 2x, we 
will get remainders that increase by 2 each time the divisor increases 
by 2.

Then we can solve the problem by the method we used on the preceding 
problem, by re-writing the given information again as follows:

    2x+3 = 5 = 0 mod 5
    2x+3 = 7 = 0 mod 7
    2x+3 = 9 = 0 mod 9
    2x+3 = 11 = 0 mod 11

The solution to the problem is then found by first finding the number 
n that is the smallest whole number divisible by 5, 7, 9, and 11; then 
the answer to the problem is the number x for which n = 2x+3.

I hope you can follow all this, and that it helps. Please write back 
if you have further questions on this.

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

Date: 11/11/2001 at 23:02:53
From: Doctor Peterson
Subject: Re: Remainders

Here's a quick hint.

I first notice that when the divisor increases by 2, the remainder 
increases by 1. I am aware of a similar kind of problem where the 
remainder increases by 1 when the divisor increases by only 1, which 
has an almost easy solution. (Easy when you see it!) This problem can 
be transformed to that kind by thinking about 2x rather than x, the 
number we're looking for.

We can express the statements about remainders by saying that there 
are integers a, b, c, and d for which

    x =  5a + 1
    x =  7b + 2
    x =  9c + 3
    x = 11d + 4

Now double each of these equations:

    2x =  5(2a) + 2
    2x =  7(2b) + 4
    2x =  9(2c) + 6
    2x = 11(2d) + 8

I did that so that the remainders are now counting by twos, as the 
divisors are. That lets me use the trick I know: since each remainder 
is now 3 less than the corresponding divisor, I can add 3 to both 
sides and eliminate remainders entirely:

    2x + 3 =  5(2a) +  5 =  5(2a+1)
    2x + 3 =  7(2b) +  7 =  7(2b+1)
    2x + 3 =  9(2c) +  9 =  9(2c+1)
    2x + 3 = 11(2d) + 11 = 11(2d+1)

This tells use that 2x+3 is a multiple of 5, 7, 9, and 11. (We don't 
need to worry about what a, b, c, and d are.) Find the smallest number 
that fits that, and then solve to find x.

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