# remainder problem based on 5 and 7

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?

-
Chinese Remainder Theorem. – anon Aug 27 '12 at 15:47

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.

-
thank you very much..:) – honeywell Aug 27 '12 at 16:23

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.

-

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.

-