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.

When a number is divided by 5 than remainder is 2 and when the same number is divided by 7 remainder is 4. What will be remainder be when the same number is divided by 35?

What is the concept behind it and if there such any concept please share with us. How to solve such problem in less time?

share|improve this question
3  
Chinese Remainder Theorem. –  anon Aug 27 '12 at 15:47
add comment

3 Answers

up vote 2 down vote accepted

Here is a little trick that works only in a small proportion of cases, including this one.

Note that $2=-3+5$ and $4=-3+7$. So $-3$ has remainder $2$ on division by $5$, and remainder $4$ on division by $7$. Thus an answer to our problem is $-3$. (If you doubt that, for example, $-3$ has remainder $2$ on division by $5$, note that $-3=(-1)(5)+2$. So the quotient when you divide $-3$ by $5$ is $-1$, and the remainder is $2$.)

We may not like $-3$ as an answer, because it is negative, and there is still a widespread prejudice against negative numbers. But if we add $35$ to $-3$, we do not change the remainder on division by $5$ or by $7$. So a positive answer is $32$.

Here is a more complicated puzzle you can solve in the same way. Find a positive number which has remainder $1$ on division by $2$, remainder $2$ on division by $3$, remainder $4$ on division by $5$, and remainder $6$ on division by $7$. We note that $-1$ works, apart from being regrettably not positive. But if we add $(2)(3)(5)(7)$ to $-1$, the remainders do not change. So an answer to this new problem is $209$.

Except in this sort of very special case, or when numbers are quite small, we need more general tools. In your case, the numbers are small, so we can start with $4$, which has the right remainder on division by $7$. Keep adding $7$ to this until we get something that has the right remainder on division by $5$.

For general tools, see the Wikipedia article on the Chinese Remainder Theorem, or any introductory book on Number Theory.

share|improve this answer
    
thank you very much..:) –  honeywell Aug 27 '12 at 16:23
add comment

Hint $\, $ $\rm n\equiv -3\:$ mod $\rm 5,7\:\Rightarrow\:n\equiv -3\ mod\ 35,\:$ i.e. $\rm\:5,7\:|\:n\!+\!3\:\Rightarrow\:35\:|\:n\!+\!3,\:$ by $\rm\:35 = lcm(5,7).$

Remark $\ $ This constant-case optimization of CRT is frequently useful in practice.

share|improve this answer
add comment

n = 5a + 2 = 7b + 4; a and b both are integers. so 5a = 7b + 2. The multiples of 5 ends in either 0 or 5, meaning 7b = a number ends in 8 or 3, so it could be 28, or 63 and b could be 4 or 9. Substitute 4 or 9 as b back into expression of n, n is either 67 or 32 and both gives reminder of 32 when divided by 35.

share|improve this answer
add comment

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.