0
$\begingroup$

I am having difficulty solving the following problem:

Marge has n candies , where n is an integer between 20 and 50.If marge divides the candies equally among 5 children she will have 2 candies remaining . If she divided the candies among 6 children she will have 1 candy remaining.How many candies remain if she divides the candies among 7 children ?

The equation I got was $5q-6k+1=0$

I tried using this method but I dont think it will work here. Any suggestions on how I could solve this ?I would appreciate it if the method involves equations instead of plugging in numbers and testing.

  • 1
    Let me try using congruences and will post back2012-07-19

3 Answers 3

1

This is a classic Chinese Remainder Theorem. We know that $\begin{align*} n &\equiv 2\pmod{5}\\ n &\equiv 1\pmod{6}. \end{align*}$ By the Chinese Remainder Theorem, there is a unique number $n$ modulo $30=5\times 6$ that satisfies both equations.

We can compute it directly: $n=5q+2$ since it leaves a remainder of $2$ when divided by $5$. That means that we must have $5q+2\equiv1\pmod{6}$, which means $5q\equiv -1\equiv 5\pmod{6}$, hence $q\equiv 1\pmod{6}$. So $n=5q+2 = 5(6k+1)+2 = 30k+5+2 = 30k+7$. That is, the solution is $n\equiv 7\pmod{30}$.

Since the number must be between $20$ and $50$, the number is $37$. When divided among $7$ children, she will have $2$ candles left over.

If you must avoid congruences (really, you are only avoiding them explicitly, shoving them "under the carpet"), $n$ must be of the form $6k+1$. We can rewrite this as $n=6k+1 = 5k + (k+1)$. Since, when $n$ is divided by $5$ the remainder is $2$, that means that when we divide $k+1$ by $5$ the remainder is $2$. Therefore, the remainder when dividing $k$ by $5$ must be $1$ (so that the remainder of $k+1$ will be $1+1=2$), so $k=5r+1$. So $n=6k+1 = 6(5r+1)+1 = 30r+7$, and we are back in what we had above.

  • 0
    That definitely makes sense. Thanks..2012-07-20
1

Hint $\rm\,\ n = 6j\!+\!1,\,\ 5\:|\:n\!-\!2 = 6j\!-\!1\:\Rightarrow\:5\:|\:j\!-\!1\:\Rightarrow\:j = 5k\!+\!1\:\Rightarrow\: n = 6(5k\!+\!1)\!+\!1 = 30k\!+\!7$

  • 0
    @Rajeshwar $\rm\ A\:|\:B\:$ means $\rm\:A\:$ divides $\rm\:B\ \ $2012-07-19
0

Find all the numbers between $\,30\,$ and $\,50\,$ that give a remainder of $\,2\,$ when divided by $\,5\,$ (there are $\,6\,$). From these, choose the numbers that give a residue of $\,1\,$ when divided by $\,6\,$ (there's only $\,1\,$ such number out of the above six). Now calculate the remainder of this one number when divided by $\,7\,$ (solution: $\,2\,$)