Associated Topics || Dr. Math Home || Search Dr. Math

### 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

- 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/

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
Math Forum Home || Math Library || Quick Reference || Math Forum Search