Divisibility and Remainders on the GMAT

In this post, I would like to focus on a particular type of remainder questions and how to solve them in a particular way. For the type of questions I am going to discuss today, I like to use “Binomial Theorem.” You might be tempted to run away right now and save yourself some precious time if you are not a Math geek but wait! We will just use an application of Binomial which I will explain in very simple language. I am quite certain that you will be comfortable with the method if you just give it a chance.

Question 1: What is the remainder when \(\frac{(3^{84})}{26}\)

(A) 0
(B) 1
(C) 2
(D) 24
(E) 25

Solution: First up, GMAT questions don’t involve any painful calculations. So my thought is that there has to be an obvious link between 3 and 26. 26 is 1 less than the cube of 3. (It helps one to know the squares of first 20 numbers and cubes of first 10 numbers.)

So, \(3^3 = 27\)

But how is it going to help us? Now we come to binomial theorem. Let me start with something you already know.

\((a + b)^2 = a^2 + 2ab + b^2\)

\((a + b)^3 = a^3 + 3ba^2 + 3ab^2 + b^3\)

What about \((a + b)^4\) or \((a + b)^5\) or higher powers? Binomial theorem just tells us how to expand these expressions. It gives you a general formula:

(a + b)^n = a^n + n*a^(n-1)*b + n(n-1)/2*a^(n-2)*b^2 +……..+ n*a*b^(n-1) + b^n

I know the above looks intimidating but our concern is limited to the last term of the expression. Notice that every term above is divisible by ‘a’ except for the last term b^n. Every term but the last has ‘a’ as a factor. That is all you need to understand about Binomial Theorem.

Now for some quick applications:

What is the last term when you expand \((8 + 1)^{20}\)? It is 1^20 (which is just ‘1’).

When you expand \((8 + 1)^{20}\), is every term divisible by 8? Yes, except for the last term, 1, because every term has 8 as a factor except for the last term.

If I divide \((8 + 1)^{20}\) by 8, what will be the remainder? Since every term (except for the last one) in the expansion of \((8 + 1)^{20}\) is divisible by 8, we can say that \((8 + 1)^{20}\) is 1 more than a multiple of 8. Hence the remainder when we divide it by 8 will be 1.

Or I can say that when I divide \(9^{20}\) (which is just \((8 + 1)^{20}\) by 8, the remainder is 1.

Now let’s look at our original question.

\((3^{84}) = (3^3)^{28} = 27^{28} = (26 + 1)^{28}\)

Every term of \((26 + 1)^{28}\) will be divisible by 26 except for the last one. The last term will be 1^28 = 1. Hence, when you divide 27^28 by 26, the remainder will be 1.

Answer (B). This question is discussed HERE.

All you had to do was to look for a power of 3 which is 1 more or 1 less than 26. We found that the third power of 3 is 1 more than 26. We adjusted the power to make 27 the base and split it into (26 + 1). We got the remainder as 1. Why do we necessarily look for a power 1 more or 1 less? We do that because 1^n is always 1. If we are left with 2^28, we again have a problem since we don’t know what 2^28 is. Let’s use this concept in another problem now:

Question 2: What is the remainder when 2^86 is divided by 9?

(A) 1
(B) 2
(C) 3
(D) 4
(E) 8

I have added a few complications in this question. Let’s tackle them one by one. We start by looking for a power of 2 which is 1 more or 1 less than 9. We know 2^3 = 8 which is 1 less than 9.

Next, let’s adjust the power to make the base 8.

\(2^{86} = 8^?\)

86 is not divisible by 3. The closest integer less than 86 that is divisible by 3 is 84. So, separate out two 2s and work with the rest of the 84 2s as of now.

\(2^{86} = (2^2) * (2^{84}) = (4) * (2^3)^{28} = 4* (8^{28})\)

I am going to forget about the 4 for the time being.

\(8^{28} = (9 – 1)^{28} = [9 + (-1)]^{28}\)

Every term of this expression will be divisible by 9 except for the last term \((-1)^{28}\) which is again equal to 1.

Hence, 8^28 will give a remainder 1 when divided by 9.

I can say that \(8^{28} = 9m + 1\) where m is some positive integer. Now, we need to consider the 4 that we left out in the previous step. Our actual expression is

\(4 * 8^{28} = 4 * (9m + 1) = 4*9m + 4\)

When I divide this by 9, 4*9m is divisible by 9. So, 4*9m + 4 is 4 more than a multiple of 9. Hence the remainder will be 4.

This question is discussed HERE.

A question to ponder on: How will you solve this question if I change it to “What is the remainder of 2^83 is divided by 9?”

Let’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

Solution: 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.

This question is discussed HERE.

Above, we have been focusing on Divisibility and Remainders. There are some more ‘types’ of remainder questions. Let’s take them one by one so that by the end of it all, you are an expert in everything related to remainders. In this post I will start with a question similar to what you mind find in the Official Guide for GMAT Review.

Question: If a and b are positive integers such that a/b = 97.16, which of the following cannot be the remainder when a is divided by b?

(A) 4
(B) 12
(C) 22
(D) 28
(E) 96

Some of my most brilliant students have asked me something similar to this: “When I divide 11 by 4, I get 2.75. What do you mean by, “What is the remainder?’ Where is it?’” So if it is bothering you as well, don’t worry; I will address this issue first.

Say, I tell you the following: Divide 11 by 4. What do you get?

You could answer me with one of the following:

Case 1: You could say, “I get 2.75”

Case 2: You could say, “I get 2 as the quotient and 3 as the remainder.”

Either ways, you are correct. 11/4 = (2 ¾)

When you use the decimal form, you get a .75 which you add to 2 to give you 2.75. This .75 is nothing but the way you express the remainder 3. When you divide 11 by 4, 4 goes into 11 two times and then 3 is left over. When 4 goes into 3, you get 0.75 which is ¾. That is the reason why you can write 11/4 as (2 ¾) in mixed fractions.

Do the following calculations and see what you get. Express the answer in both the forms – Decimal form and quotient-remainder form.

1. Divide 22 by 8.
2. Divide 55 by 20.
3. Divide 275 by 100.

Let’s see what we get in each case.

1. Divide 22 by 8.

Case 1: In decimal form we get 2.75

Case 2: In quotient-remainder form we get 2 as quotient and 6 as remainder (Remember, the divisor is 8 here). We can say 22/8 = 2 (6/8) in mixed fractions.

1. Divide 55 by 20.

Case 1: In decimal form we get 2.75

Case 2: In quotient-remainder form we get 2 as quotient and 15 as remainder (Remember, the divisor is 20 here). We can say 55/20 = 2 (15/20) in mixed fractions.

1. Divide 275 by 100.

Case 1: In decimal form we get 2.75

Case 2: In quotient-remainder form we get 2 as quotient and 75 as remainder (Remember, the divisor is 100 here). We can say 275/100 = 2 (75/100) in mixed fractions.

Notice that the remainder is different in each case above. As the divisor changes, the remainder changes even though in decimal form the answer is the same. This is so because in each of the above cases, 6/8 = 0.75, 15/20 = 0.75 and 75/100 = 0.75. Each of these fractions is equal to ¾. Now if I flip the question and say, “When I divide a by b, I get 2.75. Which of the following cannot be the remainder when a is divided by b: 2, 3, 6, 12, 15?”

We saw above that 2.75 = 2 (75/100) = 2 ¾ in the lowest form. So the remainder will be 3 if the divisor is 4. The remainder will be 6 if the divisor is 8. The remainder will be 15 if the divisor is 20. On the same lines, the remainder will be 12 if the divisor is 16 because 12/16 = ¾. Can the remainder be 2?

3/4 = 2/?

We cannot have an integer value in place of the ‘?’. Hence we will never get 2 as the remainder. The remainder will always be a positive multiple of 3.

Let’s go back to the original question now: If a and b are positive integers such that a/b = 97.16, which of the following cannot be the remainder when a is divided by b?

a/b = 97.16 = 97 (16/100) in mixed fraction = 97 (4/25) in the lowest form.

The remainder must be a positive multiple of 4. 22 is not a multiple of 4 hence you can never have 22 as the remainder

4/25 = 22/?

You cannot have an integer in place of the ‘?’

Hence answer is 22.

Let me end this post with a question for you: If a and b are positive integers such that a/b = 82.024, which of the following can be the value of b?

(A) 100
(B) 150
(C) 200
(D) 250
(E) 550

Hopefully, you will arrive at the answer in a few seconds!

We have looked at various types of GMAT remainder questions and discussed how to tackle them in a few previous posts. There is one concept, however, that we haven’t discussed yet, and that is using ingenuity on remainder questions.

Say “x” gives you a remainder of 2 when divided by 6. What will be the remainder when x + 1 is divided by 6?

Go back to the divisibility concepts discussed above. When x balls are split into groups of 6, we will have 2 balls leftover. If we are given 1 more ball, it will join the 2 balls and now we will have 3 balls leftover. The remainder will be 3.

What happens in the case of x + 6 – what will be the remainder when this is divided by 6? This additional 6 balls will just make an extra group of 6, so we will still have 2 balls leftover.

What about the case of x + 9? Now, of the extra 9 balls, we will make one group of 6 and will have 3 balls leftover. These 3 balls will join the 2 balls leftover from x, giving us a remainder of 5.

Now, what about the case of 2x? Recall that 2x = x + x. The number of groups will double and so will the remainder, so 2x will give us a remainder of 2*2 = 4.

On the other hand, if x gives us a remainder of 4 when divided by 6, then 2x divided by 6 will have a remainder of 2*4 = 8, which gives us a remainder of 2 (since another group of 6 will be formed from the 8 balls).

Let’s consider the tricky case of x^2 now. If x gives us a remainder of 2 when it is divided by 6, it means:

\(x = 6Q + 2\)

\(x^2 = (6Q + 2)*(6Q + 2) = 36Q^2 + 24Q + 4\)

Note here that the first and the second terms are divisible by 6. The remainder when you divide this by 6 will be 4.

We hope you understand how to deal with these various cases of remainders. Let’s take a look at a GMAT sample question now:

Question: If z is a positive integer and r is the remainder when z^2 + 2z + 4 is divided by 8, what is the value of r?

Statement 1: When (z−3)^2 is divided by 8, the remainder is 4.

Statement 2: When 2z is divided by 8, the remainder is 2.

Solution: This is not our typical, “When z is divided by 8, r is the remainder” type of question. Instead, we are given a quadratic equation in the form of z that, when divided by 8, gives us a remainder of r. We need to find r. This question might feel complicated, but look at the statements – at least one of them gives us data on a quadratic! Looks promising!

Statement 1: When (z−3)^2 is divided by 8, the remainder is 4

\((z – 3)^2 = z^2 – 6z + 9\)

We know that when \(z^2 – 6z + 9\) is divided by 8, the remainder is 4. So no matter what z is, \(z^2 – 6z + 9 + 8z\), when divided by 8, will only give us a remainder of 4 (8z is a multiple of 8, so will give remainder 0).

\(z^2 – 6z + 9 + 8z = z^2 + 2z + 9\)

\(z^2 + 2z + 9\) when divided by 8, gives remainder 4. This means \(z^2 + 2z + 5\) is divisible by 8 and would give remainder 0, further implying that \(z^2 + 2z + 4\) would be 1 less than a multiple of 8, and hence, would give us a remainder of 7 when divided by 8. This statement alone is sufficient.

Let’s look at the second statement:

Statement 2: When 2z is divided by 8, the remainder is 2

\(2z = 8a + 2\)

\(z = 4a + 1\)

\(z^2 = (4a + 1)^2 = 16a^2 + 8a + 1\)

When z^2 is divided by 8, the remainder is 1. When 2z is divided by 8, the remainder is 2. So when \(z^2 + 2z\) is divided by 8 the remainder will be 1+2 = 3.

When \(z^2 + 2z + 4\) is divided by 8, remainder will be 3 + 4 = 7. This statement alone is also sufficient. Because both statements alone are sufficient, our answer is D. Discussed HERE.

Let's continue on our endeavor to understand divisibility and remainders in this post. Last week’s post focused on situations where the remainders were equal. Today, let’s see how to deal with situations where the remainders are different.

Question: When positive integer n is divided by 3, the remainder is 2. When n is divided by 7, the remainder is 5. How many values less than 100 can n take?

(A) 0
(B) 2
(C) 3
(D) 4
(E) 5

Solution: So n is a number 2 greater than a multiple of 3 (or we can say, it is 1 less than the next multiple of 3). It is also 5 greater than a multiple of 7 (or we can say it is 2 less than the next multiple of 7)

\(n = 3a + 2 = 3x – 1\)
\(n = 7b + 5 = 7y – 2\)

No common remainder! When we have a common remainder,the smallest value of n would be the common remainder. Say, if n were of the forms: (3a + 1) and (7b + 1), the smallest number of both these forms is 1. When 1 is divided by 3, the quotient is 0 and the remainder is 1. When 1 is divided by 7, the quotient is 0 and the remainder is 1. But that is not the case here. So then, what do we do now? Let’s try and work with some trial and error now. n belongs to both the lists given below:

Numbers of the form (3a+2): 2, 5, 8, 11, 14, 17, 20, 23, 26, 29, 32, 35, 38, 41, 44, 47, 50…

Numbers of the form (7b + 5): 5, 12, 19, 26, 33, 40, 47, 54, 61, 68, 75…

Which numbers are common to both the lists? 5, 26, 47 and there should be more. Do you see some link between these numbers? Let me show you some connections:

– 26 is 21 more than 5.
– 47 is 21 more than 26.
– 21 is the LCM of 3 and 7.

How do we explain these? Say, we identified that the smallest positive number which gives a remainder of 2 when divided by 3 and a remainder of 5 when divided by 7 is 5 (note here that when we divide 5 by 7, the quotient is 0 and the remainder is 5). What will be the next such number? Since the next number will also belong to both the lists above so it will be 3/6/9/12/15/18/21… away from 5 and it will also be 7/14/21/28/35/42… away from 5 i.e. it will be a multiple of 3 and a multiple of 7 away from 5. The smallest such multiple is obviously the LCM (lowest common multiple) of 3 and 7 i.e. 21. Hence the next such number will be 21 away from 5. We get 26. Use the same logic to get the next such number. It will be another 21 away from 26 so we get 47. By the same logic, the next few such numbers will be 68, 89, 110 etc. How many such numbers will be less than 100? 5, 26, 47, 68, 89 i.e. 5 such numbers.

So, does this mean that when the remainders are not equal, you will need to make the lists given above. Well yes, in a way, but you can do it mentally. Let me explain. In the first 100 numbers, there will be many more numbers of the form (3a+2) than (7b + 5). Since n should be of both the forms, let’s start checking in the smaller list first.

Say b = 0, the number is 5. Is 5 of the form (3a + 2). Yes! Your list has served its purpose. Now all we need to do is keep adding 21 (the LCM of 3 and 7) to get the next few numbers! This turned out to be an easy example. Let’s change the values a little to make it a little more cumbersome.

This question is discussed HERE.

Question: When positive integer n is divided by 13, the remainder is 2. When n is divided by 8, the remainder is 5. How many such values are less than 180?

(A) 0
(B) 1
(C) 2
(D) 3
(E) 4

Solution: The LCM of 8 and 13 is 104. Hence there cannot be more than 2 such values less than 180. Options (D) and (E) are out of the window for sure.

The number n should be of the following two forms:

\(n = 8a + 5\)
\(n = 13b + 2\)

In a given bunch of numbers, there will be many more numbers of the form (8a + 5) and fewer of the form (13b + 2) so let’s start with a number of the form (13b + 2).

If b = 0, n = 2. Is it of the form (8a + 5)? No. n/8 gives a remainder of 2, not 5.
If b = 1, n = 15. Is it of the form (8a + 5)? No. n/8 gives a remainder of 7, not 5.
If b = 2, n = 28. Is it of the form (8a + 5)? No. n/8 gives a remainder of 4, not 5.
If b = 3, n = 41. Is it of the form (8a + 5)? No. n/8 gives a remainder of 1, not 5.
If b = 4, n = 54. Is it of the form (8a + 5)? No. n/8 gives a remainder of 6, not 5.
If b = 5, n = 67. Is it of the form (8a + 5)? No. n/8 gives a remainder of 3, not 5.
If b = 6, n = 80. Is it of the form (8a + 5)? No. n/8 gives a remainder of 0, not 5.
If b = 7, n = 93. Is it of the form (8a + 5)? Yes! n/8 gives a remainder of 5.

The smallest value of n is 93. The next value of n = 93 + 104 = 197 i.e. greater than 180. Hence there is just one value of n less than 180. Let me continue the steps above just for kicks…

If b = 8, n = 106. Is it of the form (8a + 5)? No. n/8 gives a remainder of 2, not 5.
If b = 9, n = 119. Is it of the form (8a + 5)? No. n/8 gives a remainder of 7, not 5.

Do you see that we have started getting the same remainders again in the same order: 2, 7…? 106 is 104 more than 2. 119 is 104 more than 15. Also notice that we got all possible remainders for 8 (0, 1, 2, 3, 4, 5, 6, 7) while n was less than 104, the LCM of 8 and 13. Can you reason it out? I will leave you here with your thoughts...

This question is discussed HERE.

I will add another level of complexity to the last question we tackled in last post.

Question: A number when divided by 3 gives a remainder of 1. How many distinct values can the remainder take when the same number is divided by 9?

Now imagine that there are lots of groups of 3 and 1 ball is leftover. We don’t know exactly how many groups of 3 there are. There could be zero and there could be a 100 but let’s assume that there are many. It would look something like this:



Now, we have to make groups of 9 out of these so we start combining three groups of 3s to make a group of 9. Let’s see what the possibilities at the end are.

1. All groups of 3s get used to make groups of 9 and the 1 ball from before is again leftover.



2. One group of 3 and the 1 ball from before, giving you a total of 4 balls, are leftover.



3. Two groups of 3 and the 1 ball from before, giving you a total of 7 balls, are leftover.



(Three or more groups of 3 cannot be leftover because then, we will be able to make another group of 9 out of them. This is the reason why the remainder will never be 9 or greater than 9.)

Therefore, you can have the remainder in three distinct ways: 1, 4 and 7.

Now, let’s apply what we have learned to a GMAT Data Sufficiency question.

Question: What is the remainder when n is divided by 26, given that n divided by 13 gives “a” as the quotient and “b” as the remainder? (a, b and n are positive integers)

(1) a is odd
(2) b = 3

Solution: This means that out of “n” balls, if we make groups of 13, we will be able to make “a” groups and will have “b” balls leftover.

What happens when we try to combine two groups of 13 to make a group of 26? There are two possibilities: all groups of 13 will be used to make groups of 26 and “b” balls will be leftover (as before) or one group of 13 and “b” balls will be leftover.

What will decide whether a group of 13 will be leftover? If “a” is 2 i.e. we have two groups of 13, we will be able to make one group of 26 and no group of 13 will be leftover. If “a” is 3 i.e. we have three groups of 13, we will be able to make one group of 26 and one group of 13 will be leftover. If “a” is 4 i.e. we have four groups of 13, we will be able to make two groups of 26 and no group of 13 will be leftover. What do you conclude from these examples? If “a” is even, we will have no group of 13 leftover. If “a” is odd, we will have one group of 13 leftover. So the remainder when n is divided by 26 will depend on whether a is odd or even and the value of “b.” Let us look at the statements now:

Statement 1: a is odd.

If “a” is odd, then a group of 13 will be leftover. So the remainder will be 13 + b. But we do not know the value of “b.” So this statement alone is not sufficient.

Statement 2: b = 3

We now know that b = 3 but from this statement alone, we do not know whether a is odd or even. So this statement alone is not sufficient.

Taking both statements together, we know that remainder is 13+3 = 16. Hence both statements together are sufficient.

Answer (C). This question is discussed HERE.

Today we will discuss the logic behind common factors (other than 1) of two numbers.

Without actually finding all the factors of two numbers, how do we know whether they have any common factors (ignoring 1)?

Let’s take some examples:

• If the integers are even, we know that they must have at least one common factor – 2. Let’s say we have two numbers 476 and 478. How many common factors can they have? We know that 2 is a factor common to them. Can they have any other common factor? Note that the difference between them is 2. So if 4 were a factor of 476, could it be a factor of 478? No. If 4 were a factor of 476, it would be a factor of 480 next (4 away from 476). Similarly, if 7 were a factor of 476, it would not be a factor of 478, definitely. It would be a factor of 483 (7 away from 476). In fact, since the difference between the two numbers is 2, the only factor they can have in common is 2.

• Now consider that the two numbers are 476 and 484. They have a difference of 8 between them. The common factors they can have are 2, 4 and 8 (the factors of 8). If any of these factors is a factor of 476, it will be a factor of 484 too. Obviously, 476 and 484 will have many other factors but they will not have any other common factor. 7 is a factor of 476. The next multiple of 7 will be 483 and the next will be 490. 7 cannot be a factor of 484.

• What happens when both integers are odd? Say 523 and 529. The difference between them is 6. The factors of 6 are 2 and 3. Both 523 and 529 are odd numbers so 2 cannot be their factor. If 3 is a factor of 523, it will be a factor of 529 too else it will not be a factor of both the numbers. Any other number can be a factor of one of them, but not both.

This is what we can deduce:

The only factors that CAN be common (it’s not necessary that they will be common) between two numbers are the factors of the difference between them.

If any factor of the difference between them is a factor of one of the numbers, it will be a factor of the other number too. If it is not a factor of one number, it will not be a factor of the other number.

Take a look at a question based on these concepts:

Question: Given that x is a positive integer, what is the greatest common divisor (GCD) of the two positive integers, (x+m) and (x-m)?

Statement 1: \(m^2 – 10m + 16 = 0\)

Statement 2: \(x + 26\) is a prime number.

Solution:

The two given positive integers are (x + m) and (x – m). x is a positive integer so m must be an integer too. Whether m is positive or negative, we don’t know.

To know the GCD of two numbers, we need to know their common divisors. As of now, we have no idea about their common divisors, but we know that the difference between the two numbers is 2m. Their common factors must be factors of 2m.

Let’s look at the two statements:

Statement 1: \(m^2 – 10m + 16 = 0\)

We know that the quadratic will give us two values for m so we will not be able to find a unique value for m. But let’s solve it in case we get some other clues from it.

\(m^2 – 10m +16 = 0\)

\(m^2 – 2m – 8m + 16 = 0\)

\(m (m – 2) – 8 (m – 2) = 0\)

\((m – 2)*(m – 8) = 0\)

m is either 2 or 8. So 2m is either 4 or 16.

The factors of 2m will be 1, 2 and 4 and additionally, 8 and 16 (if 2m is 16). We have no idea whether x+m and x-m will have these factors so this statement alone is not sufficient.

Statement 2: \(x + 26\) is a prime number.

What does it tell us about x? Other than 2, all prime numbers are odd numbers. Since x is a positive integer,  x+26 cannot be 2. It must be a prime number greater than 2 and hence, must be odd. But 26 is even. So x must be an odd integer (Odd + Even = Odd). But we have no information about m so this statement alone is not sufficient.

Using both statements together, since x is an odd integer and m is definitely even (either 2 or 8), both the numbers (x + m) and (x – m) are odd integers. Odd integers will not have any of these factors: 2, 4, 8, 16.

So (x + m) and (x – m) must have 1 as the only common factor. Hence their greatest common divisor must be 1.

Together, the two statements are sufficient to answer the question.

Answer (C) This question is discussed HERE.

To recap: Any common factor of two numbers has to be a factor of the difference between them. This also implies that the GCD of two numbers has to be a factor of the difference between them.

Consider this: When n is divided by 3, it leaves a remainder 1.

This means that when we divide n balls in groups of 3 balls each, we are left with 1 ball.



This also means that n is 1 MORE than a multiple of 3. Or, it also means that n is 2 less than the next multiple of 3, doesn’t it?

Say, n is 16. When you split 16 balls into groups of 3 balls each, you get 5 groups of 3 balls each and there is one ball leftover. n is 1 more than a multiple of 3 (the multiple being 15). But we can also say that it is 2 LESS than the next multiple of 3 (which is 18). Hence, the negative remainder in this case is -2 which is equivalent to a positive remainder of 1.

Generally speaking, if n is divided by m and it leaves a remainder r, the negative remainder in this case is -(m – r).

When n is divided by 7, it leaves a remainder of 4. This is equivalent to a remainder of -3.

n is 3 more than a multiple of m. It is also 2 less than the next multiple of m. This means m is 5.

This concept is very useful to us sometimes, especially when the divisor and the remainder are big numbers.

Let’s take a question to see how.

Question 1: What is the remainder when 1555 * 1557 * 1559 is divided by 13?

(A) 0
(B) 2
(C) 4
(D) 9
(E) 11

Solution: Since it is a GMAT question (a question for which we will have no calculator), multiplying the 3 numbers and then dividing by 13 is absolutely out of question! There has to be another method.

Say n = 1555 * 1557 * 1559

When we divide 1555 by 13, we get a quotient of 119 (irrelevant to our question) and remainder of 8. So the remainder when we divide 1557 by 13 will be 8+2 = 10 (since 1557 is 2 more than 1555) and when we divide 1559 by 13, the remainder will be 10+2 = 12 (since 1559 is 2 more than 1557).

So n = (13*119 + 8)*(13*119 + 10)*(13*119 + 12) (you can choose to ignore the quotient and just write it as ‘a’ since it is irrelevant to our discussion)

So we need to find the remainder when n is divided by 13.

Note that when we multiply these factors, all terms we obtain will have 13 in them except the last term which is obtained by multiplying the constants together i.e. 8*10*12.

Since all other terms are multiples of 13, we can say that n is 8*10*12 (= 960) more than a multiple of 13. There are many more groups of 13 balls that we can form out of 960.

960 divided by 13 gives a remainder of 11.

Hence n is actually 11 more than a multiple of 13.

We did not use the negative remainders concept here. Let’s see how using negative remainders makes our calculations easier here. The remainder of 8, 10 and 12 imply that the negative remainders are -5, -3 and -1 respectively.

Now n = (13a – 5) * (13a – 3) * (13a – 1)

The last term in this case is -5*-3*-1 = -15

This means that n is 15 less than a multiple of 13 i.e. actually 2 less than a multiple of 13 because when you go back 13 steps, you get another multiple of 13. This gives us a negative remainder of -2 which means the positive remainder in this case will be 11.

This question is discussed HERE.

Here we avoided some big calculations.

I will leave you now with a question which you should try to solve using negative remainders.

Question 2: What is the remainder when 3^(7^11) is divided by 5? (here, 3 is raised to the power (7^11))

(A) 0
(B) 1
(C) 2
(D) 3
(E) 4

Hint: I solved this question orally in a few secs using cyclicity and negative remainders. Don’t get lost in calculations!

This question is discussed HERE.

Here, we will discuss the question we left you with in the last post. It involves a lot of different concepts – remainder on division by 5, cyclicity and negative remainders. Since we did not get any replies with the solution, we are assuming that it turned out to be a little hard.

It actually is a little harder than your standard GMAT questions but the point is that it can be easily solved using all concepts relevant to GMAT. Hence it certainly makes sense to understand how to solve it.

Question: What is the remainder when 3^(7^11) is divided by 5? (here, 3 is raised to the power (7^11))

(A) 0
(B) 1
(C) 2
(D) 3
(E) 4

Solution: As we said last week, this question can easily be solved using cyclicity and negative remainders. What is the remainder when a number is divided by 5? Say, what is the remainder when 2387646 is divided by 5? Are you going to do this division to find the remainder? No! Note that every number ending in 5 or 0 is divisible by 5.

2387646 = 2387645 + 1

i.e. the given number is 1 more than a multiple of 5. Obviously then, when the number is divided by 5, the remainder will be 1. Hence the last digit of a number decides what the remainder is when the number is divided by 5.

On the same lines,

What is the remainder when 36793 is divided by 5? It is 3 (since it is 3 more than 36790 – a multiple of 5).

What is the remainder when 46^8 is divided by 5? It is 1. Why? Because 46 to any power will always end with 6 so it will always be 1 more than a multiple of 5.

On the same lines, if we can find the last digit of 3^(7^11), we will be able to find the remainder when it is divided by 5.

Recall from the discussion in your books, 3 has a cyclicity of 4 i.e. the last digit of 3 to any power takes one of 4 values in succession.

3^1 = 3
3^2 = 9
3^3 = 27
3^4 = 81
3^5 = 243
3^6 = 729

and so on… The last digits of powers of 3 are 3, 9, 7, 1, 3, 9, 7, 1 … Every time the power is a multiple of 4, the last digit is 1. If it is 1 more than a multiple of 4, the last digit is 3. If it is 2 more than a multiple of 4, the last digit is 9 and if it 3 more than a multiple of 4, the last digit is 7.

What about the power here 7^(11)? Is it a multiple of 4, 1 more than a multiple of 4, 2 more than a multiple of 4 or 3 more than a multiple of 4? We need to find the remainder when 7^(11) is divided by 4 to know that.

Do you remember the binomial theorem concept we discussed many weeks back? If no, check it out here.

7^(11) = (8 – 1)^(11)

When this is divided by 4, the remainder will be the last term of this expansion which will be (-1)^11. A remainder of -1 means a positive remainder of 3 (if you are not sure why this is so, check last week’s post here). Mind you, you are not to mark the answer as (D) here and move on! The solution is not complete yet. 3 is just the remainder when 7^(11) is divided by 4.

So 7^(11) is 3 more than a multiple of 4.

Review what we just discussed above: If the power of 3 is 3 more than a multiple of 4, the last digit of 3^(power) will be 7.

So the last digit of 3^(7^11) is 7.

If the last digit of a number is 7, when it is divided by 5, the remainder will be 2. Now we got the answer!

Answer (C)

Interesting question, isn’t it?

Divisibility Tips

Theory on remainders problems
Tips on remainders

Units digits, exponents, remainders problems

DS remainders problems
PS remainders problems

DS divisibility problems
PS divisibility problems

guess it can be neatly solved in algebraic way:

n=6a+4
and
n=5b+3

so 5n=5(6a+4)=30a+20
and
6n=6(5b+3)=30b+18

so n=6n-5n=30(b-a)-2

because n is an integer so b-a could be any integer that makes n>0, so b-a=c, whatever b-a is doesn't affect the remainder:

n=30c-2 and because n>30, c>=2, so you n=30(c-1)+30-2, like the result of b-a doesn't affect the remainder, nor does c-1

so

n=30c+28, the remainder is 28. This is kinda the easiest and fastest way I can figure out for this sort of remainder questions

Bunuel Hi. can you please post a small write up in which basic concepts of TIME RATE AND WORK problems are explained. THanks

Check here: work-rate-problems-all-in-one-topic-205201.html

Other important topics are here: view_important_topics.php?f=7&sk=t&sd=d

Hope it helps.

This is an awesome thread. Kudos to you guys for your efforts!

hello generis, can you help me please to get to the heart of the problem above the sentence below in red i somehow cant understand, the wording/ logic

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.

this part confuses me most of all "n is 1 more than a multiple of 3 which means it is 2 less than the next multiple of 3.

first we have this n = 3a + 1 and n = 7b + 5. And its clear but after a few tricks we get this n = 3x – 2 and n = 7y – 2 whats the point to write like this

many thanks and have a wonderful day

let me try dave13

suppose we have n=7 this can be written as n=3k+1 where n = 7, k=2
also we can write n=3a-2 where n=7 and a = 3
So if a number gives the remainder of 1 when divided by 3 same number will give -2 as remainder when you consider the next consecutive multiple.

Same is for 7 and all other number 17 = 7*2 +3 or 17=7*3-4.

Hope it helps.

Hi pushpitkc can you explain following:

what are these numbers in red ?... quotients ? or what? "Since the next number will also belong to both the lists above so it will be 3/6/9/12/15/18/21… away from 5 and it will also be 7/14/21/28/35/42… "


why there will be many more numbers of the form (3a+2) than (7b + 5) ? how can i figure that out that there are more numbers of the form (3a+2)


Numbers of the form (3a+2): 2, 5, 8, 11, 14, 17, 20, 23, 26, 29, 32, 35, 38, 41, 44, 47, 50… here, do we add divisor to remainder ?

Numbers of the form (7b + 5): 5, 12, 19, 26, 33, 40, 47, 54, 61, 68, 75… here, do we add divisor to remainder ?


What is the point of rewriting \(n = 3a + 2\) AS \(3x – 1\) and not using it in solution above ?

And \(n = 7b + 5\) AS \(7y – 2\) same here


From other solutions i see that people equate \(3a + 2 = 7b + 5\) why ? in which cases can we equate ?

thank you:-)