Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question
4  
Most of your questions just beg for congruences. Why are you not using congruences? –  Arturo Magidin Jul 19 '12 at 3:27
1  
Let me try using congruences and will post back –  Rajeshwar Jul 19 '12 at 3:28

3 Answers 3

up vote 1 down vote accepted

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.

share|improve this answer
    
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 ? –  Rajeshwar Jul 19 '12 at 3:54
    
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 ? –  Rajeshwar Jul 19 '12 at 5:04
    
@Rajeshwar $\rm\,\ 6q\!-\!q + 2\, =\, 6k\!+\!1\:\Rightarrow\:q\, =\, 1 + 6\,(q\!-\!k)\equiv 1\pmod 6\ \ $ –  Bill Dubuque Jul 19 '12 at 5:47
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. –  Arturo Magidin Jul 19 '12 at 15:12
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$. –  Arturo Magidin Jul 20 '12 at 2:31

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$

share|improve this answer
    
I don't get how you got 5|n−2=6j−1 ? –  Rajeshwar Jul 19 '12 at 4:40
    
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.\ \ $ –  Bill Dubuque Jul 19 '12 at 5:00
    
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 ? –  Rajeshwar Jul 19 '12 at 5:21
    
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). –  Bill Dubuque Jul 19 '12 at 5:28
    
@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)$. –  Rajeshwar Jul 19 '12 at 5:47

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\,$)

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.