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 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!

share|improve this question
    
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

3 Answers 3

up vote 2 down vote accepted

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$$

share|improve this answer

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!

share|improve this answer

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.

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.