When positive integer n is divided by 5, the remainder is 1. When n is

SOLUTION

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 ?

(A) 3
(B) 4
(C) 12
(D) 32
(E) 35

Positive integer n is divided by 5, the remainder is 1 --> \(n=5q+1\), where \(q\) is the quotient --> 1, 6, 11, 16, 21, 26, 31, ...
Positive integer n is divided by 7, the remainder is 3 --> \(n=7p+3\), where \(p\) is the quotient --> 3, 10, 17, 24, 31, ....

There is a way to derive general formula for \(n\) (of a type \(n=mx+r\), where \(x\) is divisor and \(r\) is a remainder) based on above two statements:

Divisor \(x\) would be the least common multiple of above two divisors 5 and 7, hence \(x=35\).

Remainder \(r\) would be the first common integer in above two patterns, hence \(r=31\).

Therefore general formula based on both statements is \(n=35m+31\). Thus the smallest positive integer k such that k+n is a multiple of 35 is 4 --> \(n+4=35k+31+4=35(k+1)\).

Answer: B.

More about deriving general formula for such problems at: https://gmatclub.com/forum/manhattan-rem ... ml#p721341
_________________

5. Divisibility/Multiples/Factors

• Theory
  Divisibility and Remainders on the GMAT
  Tips and hints: Divisibility/Multiples/Factors
  3 Deadly Mistakes you must avoid in LCM-GCD Questions
  How Well Do You Know Your Factors?
  THE MOST EFFICIENT WAY TO STUDY LEAST COMMON MULTIPLES ON THE GMAT
  
  • Questions
    The E-GMAT Primes Trio - 3 Ques on No. of factors & Prime factors
    DS Questions
    PS Questions
  
  

  6. Remainders

  
  
  • Theory
    REMAINDERS
    Remainders: Tips and hints
    Divisibility and Remainders on the GMAT
    Remainders on the GMAT
    A Remainders Shortcut for the GMAT
    All About Negative Remainders on the GMAT
    A Tricky Question on Negative Remainders
    Compilation of tips and tricks to deal with remainders
    Cyclicity and the remainders on the GMAT
    GMAT Question Patterns: Remainders
    
    • Questions
      Units digits, exponents, remainders problems
      DS Questions
      PS Questions

For other subjects:
ALL YOU NEED FOR QUANT ! ! !
Ultimate GMAT Quantitative Megathread
_________________

The rule is good to solve such problems but sometime we may just solve GMAT problems simply by observation. In this case we see that number n leaves a remainder 1 from 5 so if we add 4 to n, then the number will be divisible by 5.
Similarly, the number n leaves remainder of 3 from 7, again adding 4 to n makes it divisible by 7. So in both the cases adding 4 makes the number n divisible by both 5 and 7 and hence it should also be divisible by LCM of 5,7 i.e.35. So 4 is the answer.
It is better to remember the rule but just in case you don't then simply observe.
Thanks!

First, let us say I have a number n which is divisible by 5 and by 7. We all agree that it will be divisible by 35, the LCM of 5 and 7.

Now, if I have a number n which when divided by 5 gives a remainder 1 and when divided by 7 gives a remainder 1, we can say the number is of the form
n = 5a + 1 e.g. 5 + 1, 10 + 1, 15 + 1, 20 + 1, 25 + 1, 30 + 1, 35 + 1 etc
and
n = 7b + 1 e.g. 7 + 1, 14 + 1, 21 + 1, 28 + 1, 35 + 1 etc
So when it is divided by the LCM, 35, it will give 1 as remainder (as is apparent above)

Next, if I have a number n which when divided by 5 gives a remainder 1 and when divided by 7 gives a remainder 3, we can say the number is of the form
n = 5a + 1
and
n = 7b + 3
Now, the only thing you should try to understand here is that when n is divided by 5 and if I say the remainder is 1, it is the same as saying the remainder is -4. e.g. When 6 is divided by 5, remainder is 1 because it is 1 more than a multiple of 5. I can also say it is 4 less than the next multiple of 5, can't I? 6 is one more than 5, but 4 less than 10.
Therefore, we can say n = 5x - 4 and n = 7y - 4 (A remainder of 3 when divided by 7 is the same as getting a remainder of -4)
Now this question is exactly like the question above. So when you divide n by 35, remainder will be -4 i.e. n will be 4 less than a multiple of 35. So you must add 4 to n to make it a multiple of 35

A trickier version is: If I have a number n which when divided by 5 gives a remainder 1 and when divided by 7 gives a remainder 5, what is the remainder when n is divided by 35?
n = 5a + 1 = 5x - 4
n = 7b + 5 = 7y -2
Nothing common! Now, I will need to check for the smallest such number.
I put b = 1. n = 12. Is it of the form 5a + 1? No.
Put b = 2. n = 19. Is it of the form 5a + 1? No.
Put b = 3. n = 26. Is it of the form 5a + 1? Yes.
When 26 is divided by 5, it gives a remainder of 1. When it is divided by 7, it gives a remainder if 5.
Next such number will be 35 + 26.
Next will be 35*2 + 26
and so on...
The remainder when n is divided by 35 will be 26 (or we can say it will be -9). If we want to find the number that must be added to n to make it divisible by 35, that number will be 9.
_________________

here n is divided by 5 and 7 and remainders are 1 and 3. There is a rule wherein if the difference b/w and remainder is same then the number of obtained from LCM of 2 (here 2) numbers and the constant difference.

Here constant difference is 5-1 = 4 and 7-3 = 4
so the required number if of the form A(LCM of 5 and 7) - constant difference = 35A - 4

So to obtain a multiple of 35 we would need to add 4 to 35A - 4.
Hence B - 4

There's a nice rule that says, If, when N is divided by D, the remainder is R, then the possible values of N include: R, R+D, R+2D, R+3D,. . .
For example, if k divided by 6 leaves a remainder of 2, then the possible values of k are: 2, 2+6, 2+(2)(6), 2+(3)(6), 2+(4)(6), . . . etc.

When n is divided by 5, the remainder is 1.
So, possible values of n are 1, 6, 11, 16, 21, 26, 31, 36, 41, 46, 51, 56, 61, 66, 71, 76, etc.

When n is divided by 7, the remainder is 3.
So, possible values of n are 3, 10, 17, 24, 31, 38, 45, 52, 59, 66, 73, etc.

So, we can see that n could equal 31, or 66, or an infinite number of other values.

Important: Since the Least Common Multiple of 7 and 5 is 35, we can conclude that if we list the possible values of n, each value will be 35 greater than the last value.
So, n could equal 31, 66, 101, 136, and so on.

Check the answer choices....

Answer choice A: If we add 3 to any of these possible n-values, the sum is NOT a multiple of 35.
ELIMINATE A

Answer choice B: if we take ANY of these possible n-values, and add 4, the sum will be a multiple of 35.

So, the smallest value of k is [spoiler]4[/spoiler] such that k+n is a multiple of 35.

Answer = B

RELATED VIDEO

_________________

Video solution from Quant Reasoning starts at 26:43:
Subscribe for more: https://www.youtube.com/QuantReasoning? ... irmation=1

_________________

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 ?

(A) 3
(B) 4
(C) 12
(D) 32
(E) 35

Sol: Given n=5a+1 where a is any non-negative integer and also n=7b+3 where b is any non-negative integer.....so n is of the form

Possible values of n in case 1 : 1,6,11,16,21,26,31....
Possible value of n in case 2 : 3,10,17, 24,31...

So, n=35C+ 31....Now for K+ n to be multiple of 35 K needs to be 4 so that k+n = 35C+31+4 or 35(c+1)

Ans B.

650 level is okay
_________________

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 ?

(A) 3
(B) 4
(C) 12
(D) 32
(E) 35

Method 1

n is divided by 5, the remainder is 1 ---> \(n= 5x + 1\)
or, n + k = 5x + (1 + k)
So, n + k is divisible by 5, when (1+ k) is a multiple of 5.
Or, Possible values of k are 4, 9, 14,19, 24, 29, 33,.....

n is divided by 7, the remainder is 3 ----> \(n=7y + 3\)
Or, n + k = 7y +(3 + k)
So, n + k is divisible by 7, when (3+ k) is a multiple of 7.
Or, Possible values of k are 4, 11, 18, 25, 32, 39,.....

As the lowest common value is 4, the answer is (B).

Picked up 7 & added 3 = 10

10 gives a remainder 3 when divided by 7

Wrote down similar numbers. We are looking for numbers which would either end by 1 or 6 (so they would provide a remainder 1 when divided by 5)

10
17
24
31 ........ stop

31 is the number when divided by 5, provides remainder 1 (Its already tested that it provides remainder 3 when divided by 7)

First available multiple of 35 is 35, which is just 4 away from 31

Answer = 4

Hi all, actually we don't need pluging all those values for x,y...
n=5x+1 and n=7y+3 --> n+k=> (5x+1+k)/35 so 1+k must be a multiple of 5 if we want this expression to yield an integer so k=4
Use same logic here (7y+3+k)/35 -> 3+k must be a multiple of 7, so k=4

We can find the value of n first by just strategically find values that when divided by 5 have a reminder of 1. For example, since the remainder is 1 when n is divided by 5, n will be a [(multiple of 5) + 1] and thus must be one of the following numbers:

1, 6, 11, 16, 21, 26, 31, …

Now we have to find out which of these numbers when divided by 7, have a remainder of 3.

1/7 = 0 remainder 1

6/7 = 0 remainder 6

11/7 = 0 remainder 6

16/7 = 2 remainder 2

21/7 = 3 remainder 0

26/7 = 3 remainder 5

31/7 = 4 remainder 3

We can see that 31 is the smallest value of n that satisfies the requirement. So we must determine the value of k such that k + n is a multiple of 35. Obviously, since 4 + 31 = 35 and 35 is a multiple of 35, then the smallest positive integer value of k is 4.

Answer: B
_________________

When a number N is divided by X , the remainder is a and when N is divided by Y , the remainder is b.
if the difference between the divisor and the remainder is constant throughout, then N = LCM ( X,Y ) - difference

Lets try this logic here,
When positive integer n is divided by 5, the remainder is 1.
The difference between divisor and remainder = D = 5-1 = 4


When n is divided by 7, the remainder is 3.
The difference between divisor and remainder = D = 7-3= 4

Since Difference D is constant through out , Least possible value of N = LCM( 5 , 7) - D = LCM( 5 , 7) - 4
= 35 -4 = 31.

When you divide 31 by 5, the remainder is 1 and when you divide by 7, the remainder is 3.

What is the smallest positive integer k such that k + N is a multiple of 35 ?
Lowest possible value of N = 31 and its given that ( 31 + K ) is a multiple of 35. So smallest integer K = 4.
Such that 35 will be multiple of 35.

Option B is the correct answer.

Thanks,
Clifin J Francis,
GMAT SME

When positive integer n is divided by 5, the remainder is 1

Theory: Dividend = Divisor*Quotient + Remainder

n -> Dividend
5 -> Divisor
a -> Quotient (Assume)
1 -> Remainders
=> n = 5*a + 1 = 5a + 1

When n is divided by 7, the remainder is 3

Let quotient be b
=> n = 7b + 3

n = 7b + 3 = 5a + 1
=> 5a = 7b + 2
=> a = \(\frac{7b + 2}{5}\)

Now, only those values of "b" which will give "a" also as an integer will give us the common values of n which satisfy both n = 7b + 3 = 5a + 1 the conditions

b=4 => a = \(\frac{7*4 + 2}{5}\) = 6 => Integer
=> n = 7*4 + 3 = 28 + 3 = 31

What is the smallest positive integer k such that k + n is a multiple of 35

31 + 4 = 35 => k = 4

So, Answer will be B
Hope it helps!

Watch the following video to learn the Basics of Remainders


_________________

I understand everything until the last step, where you add 4 on both sides of the equation. Can you elaborate this?

The question asks: what is the smallest positive integer k such that k + n is a multiple of 35 ?

We got that \(n=35m+31\). 35m IS a multiple of 35 so we should add something to 31, so that 31 + k also becomes a multiple of 35. The smallest positive integer we can add to 31 such that the sum is a multiple of 35 is 4.
_________________

Hello from the GMAT Club BumpBot!

Thanks to another GMAT Club member, I have just discovered this valuable topic, yet it had no discussion for over a year. I am now bumping it up - doing my job. I think you may find it valuable (esp those replies with Kudos).

Want to see all other topics I dig out? Follow me (click follow button on profile). You will receive a summary of all topics I bump in your profile area as well as via email.
_________________