# Find the smallest multiple of 5 that have rest 2 when divided by 3 and by 4

I am trying to find the smallest multiple of $5$ that have rest $2$ when divided by $3$ and by $4$.

I know that $5x-2=3q$ and $5x-2=4p$, by the Euclidean division. Then I give values to $x$ until I find a multiple of $3$ and $4$ simultaniosly. I found $x=10$. I would like to know if there is another way to show this!

-
Chinese reminder theorem? –  dtldarek May 21 '12 at 21:38
@dtldarek: I am not allowed to use the Chinese reminder theorem. Just Euclidean division. –  spohreis May 21 '12 at 21:40
Well, it's good to know ;-) Any other constraints? –  dtldarek May 21 '12 at 21:44
@dtldarek: No. :) –  spohreis May 21 '12 at 21:50
It seems André Nicolas was much faster than me (and wrote exactly the answer I was about to give). Besides, all those arguments are somehow Chinese reminder theorem, just disguised or special cases. Anyway, good luck! –  dtldarek May 21 '12 at 22:07

From what you have written we get that $$5x - 2 = 12k = 12(k-4) +48$$ $$5x = 12(k-4) + 50$$ $$x = 12 \left(\frac{k-4}{5} \right) + 10$$ This means that $k-4 = 5m$ i.e. $k = 5m+4$. Hence, all the solutions are of the form $$x = 12m+10$$

-

My reading of the question is that you are looking for the smallest (positive) multiple of $5$ that has leaves a remainder of $2$ when divided by $3$, and also when divided by $4$. General theory says that this is less than $(3)(4)(5)$, so one only needs to search through the multiples of $5$ that are less than $60$. Quickly we find that the answer is $50$.

The search really was pretty quick. Since the remainder on division by $4$ is $2$, our number must be even, and not a multiple of $4$. That leaves $10$, $30$, and $50$. Not much work!

-

Hint $\rm\ mod\ 3,4\!:\ x \equiv \dfrac{2}5\:\Rightarrow\:mod\ 12\!:\ x \equiv \dfrac{2}{5} \equiv \dfrac{14}{-7} \equiv -2 \equiv 10$

Remark $\$ See here for more on this very useful constant-case optimization of CRT.

-