Remainder

gmatusa2010 wrote:When positive integer n is divided by 5, the remainder is 1. When n is divided by 7, the remainder is 3. What is the smallest positive integer k such that K+n is a multiple of 35?

3,4,12,32,35

To minimize k such that (n + k) is a multiple of 35, we have to find that value of n which is nearest 35.

n is of the form (5a + 1) => Possible values 6, 11, 16, 21, 26, 31, 36 etc
n is of the form (7b + 3) => Possible values 10, 17, 24, 31, 38, 45 etc

In this case the minimum value of n is nearest to 35 which is 31.

Thus k must be 4.

The correct answer is B.

gmatusa2010 wrote:Rahul,

That's exactly what I did. Just wondering if there's another way. (I think this is the fastest). Or to put it another way, just to extract more learning out of this experience. Is there anyway to combine the 5a+1 and 7b+3 to create something that will yield n=35q+ something? More theoretically/abstract approach.

There is a famous theorem related to these kind of problems; Chinese Remainder Theorem. A details discussion is available here: https://www.cut-the-knot.org/blue/chinese.shtml

I am not going into the detail of the theorem. Understanding of the theorem needs a clear knowledge of Modulo (Remainder) Arithmetic. I believe application of CRT in problems like these will consume more time unless the problem is too complicated or you are super-fluent with CRT.

In general, application of CRT in these kind of problems can be summarized as follows,

• If a positive integer n when divided by a, the remainder is p and when divided by b, the remainder is q, then n is of the form [LCM(a, b)*t + s]. Where t = 0, 1, 2.. and s is the lowest such n.

For example for this problem, s = minimum such n, i.e. 31. Thus n is of the form [LCM(5, 7)*t + s] = (35t + 31), where t is any non-negative integer.

Now you may ask that for finding s we have to go for the old list method we were using, then what is the profit of using CRT? Well, if you apply CRT properly you'll automatically get the value of s, you don't have to look for it. But if you apply this summarized version of CRT, you have to find the value of s manually.