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.
Best Answer
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.