Quarter Wit, Quarter Wisdom: Divisibility Applied to Remainders

Quarter Wit, Quarter WisdomLet’s continue our discussion of Divisibility and Remainders. If you have been preparing for GMAT for a while, I am sure you would have come across a question of the following form:

Question: When positive integer n is divided by 3, the remainder is 1. When n is divided by 7, the remainder is 5. What is the smallest positive integer p, such that (n + p) is a multiple of 21?



(A) 1
(B) 2
(C) 5
(D) 19
(E) 20

Let us try and understand what the question is saying using what we have learnt so far.

“When positive integer n is divided by 3, the remainder is 1.”

When I read this, the following is what comes to my mind:



“When n is divided by 7, the remainder is 5.”

This statement brings this image to mind:



Now, before we move ahead, we need to digress a little.

Let us say, we have a number N which is divisible by 3 and by 7. Can we say it will be divisible by 21, the LCM of 3 and 7? Sure! Since the number is divisible by both 3 and 7, it has factors of 3 and 7 in it i.e. it has 21 as a factor. Let us try to analyze this situation from the ‘diagram perspective’ we have learned recently too. When we divide N by 3, the quotient will be divisible by 7. Since the quotient decides how many groups we get, when we make groups of 3, we will get 7 groups or 14 groups or 21 groups etc. Hence we will be able to club each of the 7 groups to make groups of 21. Hence, N will be completely divisible by 21.

Let’s consider another scenario now.

If we have a number N, which when divided by 3 gives a remainder 1 and when divided by 7 gives a remainder 1, what would be the remainder when N is divided by 21?

N would be of the form:
N = 3a + 1 (groups of 3 with 1 leftover) and
N = 7b + 1 (groups of 7 with 1 leftover)

N would be one of the following numbers: 3 + 1, 6 + 1, 9+ 1, 12 + 1, 15 + 1, 18 + 1, 21 + 1 etc
It would also be found in this list:  7 + 1, 14 + 1, 21 + 1, 28 + 1, 35 + 1 etc
So when N is divided by the LCM, 21, it will give 1 as remainder (as is apparent above). What we conclude from this is that if N gives the same remainder with two numbers, it will give the same remainder for their LCM too. Why? Try to use the diagrams perspective now. If we make groups of 3, we will get 7 groups or 14 groups etc and 1 will be leftover. If we club each of the 7 groups of 3 together to make groups of 21, we will still have 1 leftover. Hence when N is divided by 21, the remainder will still be 1.

Now, let’s come back to our original question. We have a number n which when divided by 3 gives a remainder 1 and when divided by 7 gives a remainder 5. We can say the number is of the form:

n = 3a + 1

and

n = 7b + 5

Let me show you some diagrams here since the concept involved is a little tricky:



Can we say that the remainder in both the cases is (-2) since we need another 2 to make complete groups of 3 and 7? When n is divided by 3 and the remainder obtained is 1, it is the same as saying the remainder is -2. n is 1 more than a multiple of 3 which means it is 2 less than the next multiple of 3. Therefore, we can say n = 3x – 2 and n = 7y – 2.

Now this is exactly like the situation we discussed above. When we divide n by 21, remainder will be -2, i.e. the same remainder. Does it mean that if we clubbed 7 groups of 3 together to make groups of 21, we would need 2 more to complete the last group of 21? I hope you will say ‘yes’. Does this also mean that we need 2 more to make n divisible by 21? Yes, of course. Hence p must be 2.

Next week, we will discuss a trickier version of this question which needs some additional concepts. Till then, practice some similar questions to gain confidence in this concept.

Karishma, a Computer Engineer with a keen interest in alternative Mathematical approaches, has mentored students in the continents of Asia, Europe and North America. She teaches the GMAT for Veritas Prep in Detroit, and regularly participates in content development projects such as this blog!

7 Responses

  1. Arun says:

    Your posts are awesome.
    Just to clarify, can we say in the above example, n > 21.

    Thanks.

    • Karishma says:

      Not necessary. n could be 19 i.e. 2 less than the first positive multiple of 21 (which is 21 itself). On dividing by 21, it will give the remainder -2 i.e. it will be 2 less than a multiple of 21.

  2. Jayant says:

    When positive integer n is divided by 3, the remainder is 2; and when positive integer t is divided by 5, the remainder is 3. What is the remainder when the product nt is divided by 15?

    1) n-2 is divisible by 5

    2) t is divisible by 3

    Please clarify this question through the above concept

  3. Jayant says:

    I must say that the way you teach and make us understand is superb.

  4. Russ says:

    Hi Karishma,

    If one of the answer choices was -2 and one was 3, would 3 be the correct answer? We are looking for positive remainders so -2 would be out. Am I mistaken?

    • Karishma says:

      You will not have negative remainders in the options. Remainder is a primarily positive concept. We discuss negative remainders because sometimes the concept helps you get to the answer directly rather than following the circuitous positive remainder path such as in some questions solved using binomial.

Leave a Reply

Spam protection by WP Captcha-Free