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

### 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/
```
Associated Topics:
High School Number Theory

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