Smallest Number Puzzle

Date: 06/30/98 at 03:11:58
From: Dr. H. M. Behl
Subject: Find the smallest number...

Dear Dr. Math, 

One problem:

Find the smallest number which when divided by 9,13,17, and 25 leaves 
remainders 1,0,2, and 3 respectively.

Thank you.

Rohit Behl

Date: 06/30/98 at 08:09:41
From: Doctor Anthony
Subject: Re: Find the smallest number...

The relevant equations are:

      x - 1 = 9p  ......(1)
          x = 13q ......(2)
      x - 2 = 17r ......(3)
      x - 3 = 25s ......(4)  where p, q, r and s are integers.

Solving (1) and (2) we get  13q - 1 = 9p  which must be solved in 
integers for p and q.

This requires  p = 13k - 3   and q = 9k - 2  where k is ANY integer.    

A similar exercise with (2) and (3) requires

       r = 13k' + 6     q = 17k' + 8

Now solve in integers k and k' the two values of q, namely

       q = 17k' + 8 = 9k - 2  

This leads to  k = 17t + 20  where t is an integer and  q = 153t + 178

Finally we solve (2) and (4) getting  s = 13u + 3  and q = 25u + 6, 
so now we require solution in integers u and t of

       q = 25u + 6 = 153t + 178

This gives  t = 25k'' + 176   and putting  k'' = -7 we get  t = 1.

Putting t = 1 into q = 153t + 178  gives  q = 331

and so   x = 13q  =  4303  and this will be the required number.

So the smallest number which when divided by 9, 13, 17, and 25 leaves 
remainders 1, 0, 2, and 3 is  4303

  4303/9  =  478 + 1/9

  4303/13 =  331

  4303/17 =  253 + 2/17

  4303/25 =  173 + 3/25 


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

Date: 07/02/98 at 07:25:34
From: Doctor Floor
Subject: Re: Find the smallest number...

Hi Rohit,

I suppose you want to have the smallest _positive_ number that has 
remainders 1, 0, 2, and 3 when divided by 9, 13, 17, and 25 
respectively.

Since the remainder after division by 13 has to be 0, we know that the 
number N we are looking for must be a multiple of 13. Thus for some n 
we know that N = 13n.

The next step is to try to make n in such a way that 13n = 9x+1 for 
some x, so that the remainder after dividing by 9 will be 1. By trying 
we search for the smallest n for which this works. That gives n = 7, 
resulting in x = 10. But that does not yet give all possible n. Think 
of a second number n, not equal to 7, that makes 13n = 9y+1 for some 
y. Then:

   13n - 13*7 = 9y + 1 - 91
     13*(n-7) = 9y - 90
     13*(n-7) = 9*(y-10)

But then, since 13 and 9 have 1 as Greatest Common Multiple (13 and 9 
are coprime), n-7 must be a multiple of 9. Or n = 9m+7 for some m. 

So we are sure now that n must be of the form n = 9m+7, but we have 
not yet checked whether any m works. If we take n = 9m+7 for some m, 
then 13(9m+7) = 117m+91 = 9X+1 for some X. So indeed any m works.

Conclusion: N = 13n = 13(9m+7) = 117m+19 makes n a multiple of 
13 and 1 plus a multiple of 9.

In the same way you can look for the values for m that make 
117m+91 = 17y+2 for some y. And you should find that m = 17k+2. 
This results in N = 117(17k+2)+91 = 1989k+325 for some k.

In the end, again in the same way, you can look for values of k to 
make 1989k+325 = 25z+3 for some z. Well, only the smallest k is 
needed. I think you must be able to find this by yourself now.

I hope to have been of help.

Best regards,

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