# Find the mysterious number

• Mar 3rd 2013, 08:26 PM
JojoZ
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
• Mar 3rd 2013, 08:36 PM
Jame
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.
• Mar 3rd 2013, 08:54 PM
JojoZ
Re: Find the mysterious number
what is the chinese remainder theorem?
• Mar 4th 2013, 05:19 AM
HallsofIvy
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 $\displaystyle n_1$, $\displaystyle n_2$, ..., $\displaystyle n_i$, then all solutions will differ by multiples of the least common multiple of $\displaystyle n_1$, $\displaystyle n_2$, ..., $\displaystyle n_i$/
• Mar 4th 2013, 06:26 AM
Soroban
Re: Find the mysterious number
Hello, JojoZ!

Here is a rather primitive solution.

Quote:

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 $\displaystyle N$ = the number of pencils.

We are told: .$\displaystyle \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]: .$\displaystyle 4a+2 \,=\,5b+3 \quad\Rightarrow\quad a \:=\:\frac{5b+1}{4}\;\;[3]$

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

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

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

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

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

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

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