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.

  • 4
    Most of your questions just *beg* for congruences. Why are you not using congruences?2012-07-19
  • 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
    Thanks for the answer.I tried using inequalities , however I dont think I am doing them right. Could you let me know if that method could be used to calculate n ?2012-07-19
  • 0
    if $\frac{5q+2}{6}$ gives remainder 1 how did you get q=1 (mod 6). Arent you suppose to get $5q+2$ = 6k +1 ?2012-07-19
  • 0
    @Rajeshwar $\rm\,\ 6q\!-\!q + 2\, =\, 6k\!+\!1\:\Rightarrow\:q\, =\, 1 + 6\,(q\!-\!k)\equiv 1\pmod 6\ \ $2012-07-19
  • 0
    @Arturo Magidin Looks like I attempted it using Inequalities. Looks like I'll have to look up on congruent equation [link](http://www.trans4mind.com/personal_development/mathematics/numberTheory/CongruenceEquationsLinear.htm)2012-07-19
  • 1
    @Rajeshwar: What do you mean, "inequalities"? This is a problem for using **congruences**. If $n$ leaves a remainder of $1$ when divided by $6$, then it must be of the form $n=6k+1$ for some integer $k$. When you divide it by $5$, since $6k+1 =5k+k+1$, then $5$ goes evenly into $5k$, and you are left with $k+1$, so the remainder for $n$ is the same as the remainder for $k+1$. As to the equation $5q+2=6k+1$, it is useless unless you then proceed to solve it as a diophantine equation, which usually requires you to do.. you guessed it! **Congruences**.2012-07-19
  • 0
    @ArturoMagidin While reviewing this question I noticed that $n=5k + (k+1) $. Now (K+1) and 5 are the remainders when n is divided by 5. In your main post you mentioned that the remainder **$K+1$ when divided by 5 gives a remainder 2**. I thought that when n which is equal to $5k+k+1$ when divided by 5 gives a remainder 2.How did you conclude that the remainder $k+1$ when divided by 5 gives a remainder 2.Thanks in advance.2012-07-20
  • 1
    @Rajeshwar: Because when you divide $6k+1$ by $5$, the $5k$ part is **already** a multiple of $5$. Adding or subtracting multiples of five form a number does not change the remainder when you divide by $5$. E.g., $2$, $7=2+5$, $22=2+5\times 4$, $177 = 2 + 5\times35$, etc., all have the same remainder when divided by $5$. So the remainder you get when dividing $n=6k+1$ by $5$ is the same as the remainder you get when dividing $n-5k = k+1$ by $5$.2012-07-20
  • 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
    I don't get how you got 5|n−2=6j−1 ?2012-07-19
  • 0
    If Marge divides the $\rm\:n\:$ candies equally among $5$ children she will have $2$ candies remaining. If each child got $\rm\:m\:$ candies then $\rm\:n = 5m\!+\!2,\:$ so $\rm\:5m = n\!-\!2,\:$ i.e. $\rm\:5\:|\:n\!-\!2.\:$ Similarly $\rm\:n = 6j\!+\!1,\:$ hence $\rm\:n\!-\!2 = (6j\!+\!1)-2 = 6j\!-\!1 = 5j + j\!-\!1.\:$ $5$ divides that iff $\rm\,5\:|\:j\!-\!1.\ \ $2012-07-19
  • 0
    So far I got two equations $5m=n-2$ and $n-2=6j-1$ could you explain how you got $n=6(5k+1)+1$ using those two equations ?2012-07-19
  • 0
    Since $5$ divides both $\rm\:6j\!-\!1\:$ and $\rm\:5j\:$ it divides their difference $\rm\:j\!-\!1,\:$ i.e. $\rm\:j\!-\!1 = 5k,\:$ so $\rm\:j = 5k\!+\!1.\:$ Hence $\rm\:n = 6j\!+\!1 = 6(5k\!+\!1)\!+\!1 = 30k\!+\!7.\:$ This will all be much more intuitive if you learn about [modular arithmetic (congruences).](http://en.wikipedia.org/wiki/Modular_arithmetic)2012-07-19
  • 0
    @Bill.Thanks for clarifying. I got the rest of the answer , however I am still having difficulty understanding how you got $j-1=5k$ .So far on one side I have $n-2=5m$ and the other equation $n-2=5j+(j-1)$.2012-07-19
  • 0
    @Rajeshwar $ $ If $\rm\:5\:|\:A\:$ and $\rm\:5\:|\:B\:$ then $\rm\:5\:|\:A-B.\:$ Above is the special case $\rm\:A = 6j\!-\!1,\,\ B = 5j,\:$ so $\rm\:5\:|\:A\!-\!B = j\!-\!1,\:$ i.e. $\rm\:j\!-\!1 = 5k,\:$ for some integer $\rm\,k.\,$ I suggest you sharpen your algebra skills since algebra seems to be a stumbling block. $\ $2012-07-19
  • 0
    Thanks I got it , was just being confused by the "|" symbol.2012-07-19
  • 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\,$)