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/