The Smallest Number Which When Divided Leaves Specific Remainders

Date: 02/27/2010 at 08:32:22
From: Sonal
Subject: Divisibility

What is the smallest number which when divided by 3, 7, and 11 leaves
remainders 1, 6, and 5, respectively?

I understand that this involves least common multiple, but have found only
that 3, 7, and 11 have differences of 4, and cannot figure out any further.

Date: 02/27/2010 at 18:28:22
From: Doctor Rick
Subject: Re: Divisibility

Hi, Sonal.

There are some high-powered math tools that can be used to solve problems
like this -- things like the Chinese Remainder Theorem and the Extended
Euclidean Algorithm. I doubt very much that you have learned these things!

At the other end of the spectrum of ways to solve this problem is the
direct approach -- "brute-force": Go through all the whole numbers 
starting from 1, finding the remainders until you find a number that 
works. That's sure to work, but it's sure to be tedious!

We can find an in-between method that will do the trick without requiring
advanced math, but first I'll show you one idea that helps us know the
brute-force search won't go on forever.

If you take any number and add the LCM of 3, 7, and 11 to it, both these
numbers will, on division by 3, 7, and 11, have the same remainders. The
LCM is a multiple of 3, and adding a multiple of 3 doesn't change the
remainder on division by 3. Likewise, it is a multiple of 7 and of 11, so
adding that LCM doesn't change the remainders on division by 7 or 11,
either.

This means that we only have to check the numbers up to the LCM, which is

   3 * 7 * 11 = 231.

After that, the pattern of remainders will start to repeat, and we'll only
see things we've seen before. If we haven't found an answer by the time we
reach 231, we never will. (In fact, the Chinese Remainder Theorem tells us
that we WILL find an answer.)

Now for the first idea to shorten the search. We could make a list of
numbers that are 5 more than a multiple of 11: 5, 16, 27, ... Do you see
that we can just keep adding 11 each time? The list will only be 
3 * 7 = 21 numbers long, which is a lot easier to search through than a 
list of 231 numbers. And we only need to test their remainders on division 
by 3 and 7.

But we can do better! Let's apply the same idea about a repeating pattern
of remainders to a smaller problem: finding numbers that give a remainder
of 1 when divided by 3, and that give a remainder of 6 when divided by 7.
The remainder pattern repeats after LCM(3, 7) = 21. By starting with a
list of numbers that are 6 more than a multiple of 7, we only need to test
three numbers. Can you see which three numbers, and what you test them
for?

Now, every 21st whole number will have the same remainders when divided by
either 3 or 7. Write down these numbers, up to 231; this time, you will
need to write down 7 numbers. Test each of these by seeing what remainder
they give on division by 11; they already give the correct remainder when
divided by 3 or 7. When you find a number that works, you're done!

What I have described here is an "intelligent search method." Using facts 
about numbers, I reduced the "search space" (the set of numbers to be 
tested) from 231 to 21 numbers, and then to 10, while simplifying the test 
as well. Isn't that a lot easier?

My answer to you is a bit long and I hope you are interested enough to
plow through it. To tell the truth, I don't know what method an
11-year-old is expected to use to solve this problem.

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

Date: 02/28/2010 at 00:57:03
From: Sonal
Subject: Divisibility

Hi Dr. Rick,

Okay, as suggested, I applied the Chinese Remainder Theorem, and found the
answer to be 412.

The answer was supposed to be of the form ...

   77x + 33y + 21z,
   
... as 77 is the LCM of 7 and 11, 33 is LCM of 3 and 11, and 21 is the LCM
of 3 and 7.

   77x when divided by 3 should have remainder 1. So x is 2.

   33y when divided by 7 should have remainder 6. So y is 4.

   21z when divided by 11 should have remainder 5. So z is 6.

Thanks for the guidance.

Regards,

Sonal

Date: 02/28/2010 at 16:35:37
From: Doctor Rick
Subject: Re: Divisibility

Hi, Sonal.

You are not 11 years old as you said, are you? Had I known, I would not
have gone to the trouble of giving you an alternate method.

Four hundred and twelve is not the answer I got. The problem was: What is
the smallest number which when divided by 3, 7, and 11 leaves remainders
1, 6, and 5, respectively?

It's true that:

  412 = 1 (mod 3)
  412 = 6 (mod 7)
  412 = 5 (mod 11)

However, 412 is not the smallest positive integer that meets those
conditions. The Chinese Remainder Theorem says that the solution is
CONGRUENT to

   77x + 33y + 21z MODULO 3 * 7 * 11

Since 412 > 3 * 7 * 11, there is a smaller solution.

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

Date: 03/01/2010 at 01:10:28
From: Sonal
Subject: Thank you (Divisibility)

Hi Dr. Rick,

Thanks for help in solving the problem. I found the correct answer as

   412 - LCM(3, 7, 11), i.e.,
   412 - 231 = 181.

I am indeed 11 years old. I study in standard VI. It is my dad who tried
to help me with the Chinese Remainder Theorem, but it looks like he
himself has not understood much.

He has something to say. So over to him.

Regards,

Sonal

* * * * * * * * * * * * * * * * * *

Hi Dr. Rick,

This question is from a maths scholarship question paper set meant for
standard VIII. It did not come with any answer, but as per the author of
the question paper, this should be solvable by a 13/14 year-old. So in 2
years' time, Sonal is supposed to solve such problems. Sometimes she
arrives at the correct answer by applying wrong methods.

Here is the method I employed after learning from you that there is a
smaller answer than 412.

   x = 1 (mod 3)                     (i)
   x = 6 (mod 7)                     (ii)
   x = 5 (mod 11)                    (iii)
   (i) => x = 3t +1                  (iv)

Plugging this value in (ii),

   3t + 1 = 6 (mod 7)
   => 3t = 5 ( mod 7)
   => t  = 4 ( mod 7)
   => t = 7s + 4                     (v)

Plugging the value of t from (v) into (iv),

   x = 3(7s + 4) + 1 = 21s + 13      (vi)

So plugging this value of x into (iii), we get

   21s + 13 = 5 (mod 11)
   => 11s + 11 + 10s + 2 = 5 (mod 11)
   => 10s + 2 = 5 (mod 11)
   => 10s = 3 (mod 11)
   => s = 8 (mod 11)
   => s = 11u + 8                    (vii)

So plugging this value of x into (iii), we get

   21s + 13 = 5 (mod 11)
   => 11s + 11 + 10s + 2 = 5 (mod 11)
   => 10s + 2 = 5 (mod 11)
   => 10s = 3 (mod 11)
   => s = 8 (mod 11)
   => s = 11u + 8                    (vii)

From (vi),

   x = 21s + 13
   = 21(11u + 8) + 13
   => x = 231u + 181
   => For u = 0, x = 181

So the answer is 181 -- not 412, as we earlier got (for u = 1).

Regards,

Subhendu (Sonal's Dad)

Date: 03/01/2010 at 17:08:37
From: Doctor Rick
Subject: Re: Thank you (Divisibility)

Hi, Sonal.

This will be mainly for your dad, but you're welcome to listen in!

That's the answer I got, too. Your previous work could give this answer as
well. Your solution simply needed to be restated: Every solution is
congruent to 412 (mod 231). Then, noting as I did that 412 > 213, we
can obtain a smaller positive solution by finding the remainder on
division of 412 by 231 -- or by subtracting 231 from 412.

There isn't just one correct method (as you know; I think you're saying
you used two different methods). I think it's better to help Sonal use
what she already understands to solve the problem, rather than introduce
math beyond her level; therefore I just named the Chinese Remainder
Theorem but didn't go into it. Is the CRT taught to 13/14 year olds in
your country? I don't think it is in the US.

To tell the truth, though, I am not particularly skilled in number theory,
so when I came up with my alternate method, I was thinking not just what
an 11 year-old might be able to understand, but what I would rather do
myself!

Can you fill in a gap in your explanation of your work? Specifically, how
did you make this step?

  3t = 5 ( mod 7)
  t  = 4 ( mod 7)

And this one?

  10s = 3 (mod 11)
  s = 8 (mod 11)

Unless I'm missing something, filling in those gaps still requires about
as much "guess and check" as my method.

Here is a similar problem from our Archive:

  Chinese Remainder Theorem and Modular Arithmetic 
    http://mathforum.org/library/drmath/view/56010.html 

This shows how to apply the Extended Euclidean Algorithm rather than doing
any search. However, such "searchless" methods are not necessarily the 
best. If the numbers were larger, it would be better; and the algorithm 
could be implemented in a computer program better than mine.

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

Date: 03/01/2010 at 22:01:26
From: Sonal
Subject: Divisibility

Hi Dr. Rick,

The explanation of simplifying 3t = 5 ( mod 7) into t  = 4 ( mod 7) goes
like this.

Any number divided by 7 can have 7 types of remainders:

   0 
   1 
   2
   3
   4 
   5
   6
   
Three times that number will have remainders

   0 
   3 
   6
   2                     (3 * 3 = 9, 9 = 7 + 2)
   5                     (3 * 4 = 12, 12 = 7 + 5)
   1                     (3 * 5 = 15, 15 = 2 * 7 + 1)
   4                     (3 * 6 = 18, 18 = 2 * 7 + 4)

As 5 corresponds to 4, I have used that relation. As they were all unique,
this method worked. Otherwise, I could not have used the same.

Simplifying 10s = 3 (mod 11) into s = 8 (mod 11) follows the same kind of
reasoning.

Regards,

Subhendu
(Sonal's Dad)

Date: 03/01/2010 at 22:35:28
From: Doctor Rick
Subject: Re: Divisibility

Hi, Sonal.

That's what I thought. You calculated a "multiplication table" in each 
case, which amounts to trying all the possibilities to see which works 
out correctly. It turns out quite similar to my method in terms of the 
work done.

I think it's really good to see multiple methods and variations of methods
for solving the same problem. Students need to see the creativity in math
and that it isn't just following a set method. I enjoy this sort of
discussion.

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