# Calculating a number when its remainder is given

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? – 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

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.

-
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\ \$ – Gone 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
show 3 more comments

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

-

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$

-

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.\ \$ – Gone 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
– Gone 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
show 3 more comments
{"extraction_info": {"found_math": true, "script_math_tex": 0, "script_math_asciimath": 0, "math_annotations": 0, "math_alttext": 0, "mathml": 0, "mathjax_tag": 0, "mathjax_inline_tex": 89, "mathjax_display_tex": 2, "mathjax_asciimath": 0, "img_math": 0, "codecogs_latex": 0, "wp_latex": 0, "mimetex.cgi": 0, "/images/math/codecogs": 0, "mathtex.cgi": 0}, "config": {"markdown_headings": true, "markdown_code": false, "boilerplate_config": {"ratio_threshold": 0.18, "absolute_threshold": 10, "end_threshold": 15, "enable": true}, "remove_buttons": true, "remove_image_figures": true, "remove_link_clusters": true, "table_config": {"min_rows": 2, "min_cols": 3, "format": "github"}, "remove_chinese": true, "remove_edit_buttons": true, "extract_latex": true}, "english_confidence": 0.9486582279205322, "perplexity_flag": "head"}