# Thread: Find the mysterious number

1. ## Find the mysterious number

if a collection of pencils is placed in rows of 4, there are 2 left; if placed in row of 5, there are 3 left; and if placed in rows of 7, there are 5 left. what is the smallest possible number of pencils in the collection? please explain how you get the answer

2. ## Re: Find the mysterious number

You need to use the Chinese Remainder Theorem. You can translate the problem in 3 seperate congruences mod 4, mod 5, and mod 7.

3. ## Re: Find the mysterious number

what is the chinese remainder theorem?

4. ## Re: Find the mysterious number

If you don't know that you probably don't know what congruences are either so I will answer in more elementary terms.

Let n be the number of pencils.

"if a collection of pencils is placed in rows of 4, there are 2 left"
Let i be the number of rows. So n= 4i+ 2 for some integer i.

"if placed in rows of 5, there are 3 left"
Now let j be the number of rows here. So n= 5j+ 3 for some integer j

"and if placed in rows of 7, there are 5 left."
Let k be the number of rows this time. So n= 7k+ 5

We want to solve n- 7k= 5. One obvious answer is n= 5, k= 0. However, if we put 5 pencils in "rows of 5" there would be no pencil left over, not three, so we need to note that n= 5+ 7p, k= p would also give n- 7k= 5+7p- 7p= 5 for any integer p. The number of pencils is of the form n= 5+ 7p where p can be any non-negative integer.

If we take p= 1, n= 5+ 7= 12 and if we divide that into "rows of 5" we have 2 left, not 3. If we take p= 2, n= 5+ 14= 19 and if we divide that into "rows of 5" we have 4 left over, not 3. If we take p= 3, n= 5+ 21= 26 and if we divide that into "rows of 5" we have one left over, not 3. If we take p= 4, n= 5+ 28= 33 and if we divide that into "rows of 5" we have 3 left over!

But if we divide 33 pencils into "rows of 4" we have one pencil left over, not 2. So have to continue looking. In order not to interfere with the previous results, we need to add multiple of both 7 and 5: n= 33+ 35q. If we take q= 1, n= 33+ 35= 68. If we divide that into "rows of 4", we have no pencils left over. If we take q= 2, n= 33+ 70= 103. If we divide that into "rows of 4" we have 3 pencils left, not 2. If we take q= 3, n= 33+ 105= 138. If we divide that into "rows of 4", we have 34 rows with two pencils left. There must be at least 138 pencils left.

(138 plus any multiple of 4(5)(7)= 140 will also work.)

The Chinese Remainder Theorem essentially says that if you have a series of "congruence" equations, modulo $n_1$, $n_2$, ..., $n_i$, then all solutions will differ by multiples of the least common multiple of $n_1$, $n_2$, ..., $n_i$/

5. ## Re: Find the mysterious number

Hello, JojoZ!

Here is a rather primitive solution.

If a collection of pencils is placed in rows of 4, there are 2 left;
if placed in rows of 5, there are 3 left;
and if placed in rows of 7, there are 5 left.
What is the smallest possible number of pencils in the collection?

Let $N$ = the number of pencils.

We are told: . $\begin{Bmatrix}N \:=\:4a+2 & [1] \\ N \:=\:5b + 3 & [2] \\ N \:=\:7c + 5 & [3] \end{Bmatrix}\;\text{ for integers }a,b,c.$

Equate [1] and [2]: . $4a+2 \,=\,5b+3 \quad\Rightarrow\quad a \:=\:\frac{5b+1}{4}\;\;[3]$

Equate [2] and [3]: . $5b+3 \,=\,7c+5 \quad\Rightarrow\quad b \,=\,\frac{7c+2}{5}\;\;[4]$
. . . $b \,=\,c + \frac{2c+2}{5} \quad\Rightarrow\quad b \:=\:c+ \frac{2(c+1)}{5}$

Since $b$ is an integer, $2(c+1)$ must be divisible by 5.
This happens when $c = 4 + 5k$

Substitute into [4]: . $b \:=\:\frac{7(5k+4)+2}{5} \quad\Rightarrow\quad b \:=\:7k+6$

Substitute into [3]: . $a \:=\:\frac{5(7k+6)+1}{4} \:=\:\frac{35k+31}{4}\;\;[5]$
. . . . . . . . . . . . . . . $a \:=\:8k+7 + \frac{3k+3}{4} \quad\Rightarrow\quad a \:=\:8k+7 + \frac{3(k+1)}{4}$

Since $a$ in an integer, $3(k+1)$ must be divisible by 4.
This first happens when $k=3.$

Substitute into [5]: . $a \:=\:\frac{35(3)+31}{4} \quad\Rightarrow\quad a \,=\,34$

Substitute into [1]: . $N \:=\:4(34)+2 \quad\Rightarrow\quad \boxed{N \:=\:138}$