0
$\begingroup$

A person had a number of toys to distribute among children . At first he gave $2$ toys to each child , then $4$ , then $5$ ,and then $6$ , but was always left with one . But if he had given $7$ toys to each child , no toys would have been left with him . What is the smallest number of toys that he had?

Could someone give me hint as how to approach this problem. I am not able to understand it.

$\endgroup$
2
  • 3
    $\begingroup$ One approach would be to use the Chinese remainder theorem but in this case you can speed up the calculations by seeing that if he gave $60$ toys to each child he would have $1$ left over, so you are looking for an multiple of $7$ which is one more than a multiple of $60$ $\endgroup$
    – Henry
    Commented Apr 19, 2016 at 22:09
  • $\begingroup$ In other words, take LCM+1 $\endgroup$
    – N.S.JOHN
    Commented Apr 20, 2016 at 1:44

1 Answer 1

Reset to default
1
$\begingroup$

So, we notice that if the number of toys is $k$, then $k=1\pmod{2}$, $k=1\pmod{4}$, $k=1\pmod{5}$, $k=1\pmod{6}$, and $k=0\pmod{7}$. As noted in the comments, the LCM of these numbers (other than $7$) is $60$, so we also have that $k=1\pmod{60}$. We then want to solve $60a+1=7b$ for integer $a,b$. You can solve this in a number of ways, using Euclid's Algorithm to solve the Diophantine Equiation $-60x+7y=1$.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .