# Remainder problem

If the remainder when $x$ is divided by 5 equals to the remainder when x is divided by 4 then x could be any of the following a)20 , b)21 , c)22 , d)23 e)24 (Ans=(e)24)

Now I could only tell till $x-5q=x-4p$.

Using equations how can I predict the values of x ?

-
Any of (a), (b), (c), and (d) work: leave remainders of 0, 1, 2, and 3 respectively. 24 is not a valid answer, because the remainder when divided by 4 is $0$, but the remainder when divided by 5 is $4$, and $0\neq 4$. –  Arturo Magidin Jul 17 '12 at 4:30

You are better off using congruences, not equations. In any case, the solution is only well-defined up to a multiple of $20$: given any valid solution, add $20$ to it ($20$ is the lcm of $4$ and $5$), and the result is still a solution. Subtract $20$ and the same is true.

Write $x = 5k+r$, with $0\leq r\lt 5$. Then $x = 5k+r = 4k + (k+r)$.

What we know is that the remainder of dividing $x$ by $4$ must be $r$ as well. That means that the remainder of dividing $k+r$ by $4$ must be $r$; this means that $k$ itself must be a multiple of $4$ and $r$ must be smaller than $4$. That is, $k=4\ell$ for some $\ell$, and $0\leq r\lt 4$. So $x = 5k+r = 5(4\ell)+r = 20\ell + r$, with $0\leq r\lt 4$. Thus, $20$, $21$, $22$, and $23$ all work (as do $0$, $1$, $2$, and $3$, $40$, $41$, $42$, $43$, $160$, $161$, $162$, $163$, etc). But 24 does not work (remainder when dividing by $5$ is too large).

This is much easier to do with congruences, though.

-

Hint $\$ The common remainder $\rm\,r \le 3,\,$ being a remainder mod $4.\,$ Since both $4$ and $5$ divide $\rm\:x-r\:$ so too does their lcm $20.\:$ Thus $\rm\:x = 20\,k + r,\:$ for $\rm\:0\le r\le 3,\:$ hence $\rm\:x\ne 24.$

Remark $\$ This is a trivial constant case of CRT = Chinese Remainder. If $\rm\:x\equiv r\pmod{n_k}$ has a constant residue $\rm\,r\,$ for all moduli, then, as above, we infer $\rm\:x \equiv r\pmod n,\,$ for $\rm\:n = lcm\,\{n_k\}.\,$ Further, if $\rm\,r\,$ denotes a remainder (vs. congruence class),  so $\rm\, 0\le r < n_k,\,$ then $\rm\: x = j\,m + r,\:$ where $\rm\:0\le r < n_0,\,$ for $\rm\:n_0 = min\, \{n_k\},\,$ and some $\rm\,j\in\Bbb Z.$

So that's how to generally "predict the values". However, for test problems like this, it is usually quicker to brute-force search for the non-solution, since each test takes at most a few seconds.

-

If $x=5a+r$ with $0\le r\le4$ and $x=4b+r$ with $0\le r\le3$ then $5a=4b$ so $a=4c$ and $b=5c$ for some $c$, and we have $$x=20c+r{\rm\quad with\quad}0\le r\le3$$ and that equation tells you which values of $x$ work and which ones don't.

-
I lost you at $a=4c$ How did you get c here and after that ? –  Rajeshwar Jul 17 '12 at 4:49
$5a=4b$, so $5a$ is a multiple of 4, but 5 is relatively prime to 4, so $a$ is a multiple of 4, so $a=4c$ for some $c$. Similarly for $b=5d$ for some $d$. But $5a=4b$, so $20c=20d$, so $c=d$. –  Gerry Myerson Jul 17 '12 at 5:04