Author 
Message 
TAGS:

Hide Tags

Math Expert
Joined: 02 Sep 2009
Posts: 64275

Divisibility and Remainders on the GMAT
[#permalink]
Show Tags
20 Oct 2015, 11:03
Divisibility and Remainders on the GMATDivisibility Unraveled Today, I will start the topic of Divisibility. We will discuss what divisibility is at a very basic level this week and then move on to remainders in the coming weeks. So the first question is – what is division? Don’t tell me what to do to divide a number by another, tell me why you do it. What is it that you are achieving by dividing one number by another? Let me tell you what I think – I like to think that division is grouping. Not happy? Let’s look at an example then. When I divide 6 by 2, I am actually just making groups of 2 from 6 and subtracting them. 6 – 2 = 4 (One group of 2 subtracted.) 4 – 2 = 2 (Another group of 2 subtracted.) 2 – 2 = 0 (Third group of 2 subtracted.) I subtracted three groups so I get 3 as my quotient. Nothing is leftover so remainder is 0. If I were to divide 14 by 3, I would subtract 4 groups of 3 from 14 giving me a quotient of 4, and 2 will be leftover. Hence, remainder will be 2. Hopefully, this made sense to you. Now let’s look at division from the ‘divisibility angle’. Is 82 divisible by 4? What I mean to ask here is that can I subtract groups of 4 from 82 such that nothing is leftover? When I subtract 20 groups of 4 (=80) from 82, I am left with 2. I cannot make any more groups of 4. Since we have a remainder of 2, 82 is not divisible by 4. I have a fascination for diagrams. It stems in part from the fact that I wanted to be an artist but found that I have no talent in the field, and in part from the fact that I believe that diagrams help people understand the concepts better. On that note, let me draw a few diagrams to help you understand divisibility. Thereafter, you will be able to solve the tricky remainder questions quickly. Imagine numbers as balls. When I say 7, imagine 7 balls in a group. Let’s start easy: Is 7 divisible by 3? Before answering, think of the following figure: To divide by 3, I have to split 7 into groups of 3. I can make two groups of 3 and then 1 ball is leftover. Hence, when I divide 7 by 3, quotient is 2 and remainder, the ball that could not be put in a group, is 1. Similarly, what happens when I divide 12 by 3? I get 4 groups and nothing is leftover. (Is this then the diagrammatic representation of 12 = 3*4? Sure.) Then when I divide 12 by 4, I should be able to get 3 groups with nothing leftover. I guess you get the picture! Now, a question: I have a number that when divided by 6, leaves a remainder of 2. What will be the remainder when the number is divided by 3?(Do you think I moved on too quickly to too difficult a concept? Not really, just follow me) So here, I do not know what the number is, but I know that when I make groups of 6 balls each, 2 balls are leftover (as shown in the diagram below). Logically, it follows that when I split each group of 6 balls into two groups of 3 balls, I will still have the same 2 balls remaining. Since there are 2 balls leftover when groups of 3 are made, we can say that when we divide this number by 3, the remainder will still be 2! You don’t have to make the diagram in the exam of course. Just imagine it. A slight twist on the question above: I have a number that when divided by 6, leaves a remainder of 4. What will be the remainder when the number is divided by 3? Imagine the picture. Just like above but with groups of 6, there are 4 balls leftover. You divide the groups of 6 into groups of 3 – all is well till now – but then, you make another group of 3 from the 4 balls that are leftover. Therefore, only one ball will be leftover. Hence, when you divide the given number by 3, the remainder will be 1! Try a few more examples and let this theory sink in. We will delve into more details in the coming few weeks. Attachment:
Ques.jpg [ 7.24 KiB  Viewed 41471 times ]
Attachment:
Ques (1).jpg [ 10.69 KiB  Viewed 41481 times ]
Attachment:
Ques (2).jpg [ 10.52 KiB  Viewed 41459 times ]
Attachment:
Ques (3).jpg [ 27.86 KiB  Viewed 41597 times ]
_________________




Math Expert
Joined: 02 Sep 2009
Posts: 64275

Re: Divisibility and Remainders on the GMAT
[#permalink]
Show Tags
20 Oct 2015, 12:09
A Remainders Shortcut for the GMAT We firmly believe that teaching someone is a most productive learning for oneself and every now and then, something happens that strengthens this belief of ours. It’s the questions people ask – knowingly or unknowingly – that connect strings in our mind such that we feel we have gained more from the discussion than even our students! The other day, we came across this common GMAT question on remainders and many people had solved it the way we would expect them to solve. One person, perhaps erroneously, used a shortcut which upon reflection made perfect sense. Let me give you that question and the shortcut and the problem with the shortcut. We would like you to reflect on why the shortcut actually does make sense and is worth noting down in your log book. Question: Positive integer n leaves a remainder of 4 after division by 6 and a remainder of 3 after division by 5. If n is greater than 30, what is the remainder that n leaves after division by 30?(A) 3 (B) 12 (C) 18 (D) 22 (E) 28 Solution: We are assuming you know how people do the question usually: The logic it uses is discussed here and the solution is given below as Method I. Method I:Positive integer n leaves a remainder of 4 after division by 6. So n = 6a + 4 n can take various values depending on the values of a (which can be any non negative integer). Some values n can take are: 4, 10, 16, 22, 28, … Positive integer n leaves a remainder of 3 after division by 5. So n = 5b + 3 n can take various values depending on the values of a (which can be any non negative integer). Some values n can take are: 3, 8, 13, 18, 23, 28, … The first common value is 28. So n = 30k + 28 Hence remainder when positive integer n is divided by 30 is 28. Answer: E. This question is discussed HERE. Perfect! But one fine gentleman came up with the following solution wondering whether he had made a mistake since it seemed to be “super simple Math”. Method II:Given in question: “n leaves a remainder of 4 after division by 6 and a remainder of 3 after division by 5.” Divide the options by 6 and 5. The one that gives a remainder of 4 and 3 respectively will be correct. (A) 3 / 6 gives Remainder = 3 > INCORRECT (B) 12 / 6 gives Remainder = 0 > INCORRECT (C) 18 / 6 gives Remainder = 0 > INCORRECT (D) 22 / 6 gives Remainder = 4 but 22 / 5 gives Remainder = 2 > INCORRECT (E) 28 / 6 gives Remainder = 4 and 28 / 5 gives Remainder = 3 > CORRECT Now let us point out that the options are not the values of n; they are the values of remainder that is leftover after you divide n by 30. The question says that n must give a remainder of 4 upon division by 6 and a remainder of 3 upon division by 5. This solution divided the options (which are not the values of n) by 6 and 5 and got the remainder as 4 and 3 respectively. So the premise that when you divide the correct option by 6 and 5, you should get a remainder of 4 and 3 respectively is faulty, right? This is where we want you to take a moment and think: Is this premise actually faulty? The fun part is that method II is perfectly correct too. Method I seems a little complicated when compared with Method II, doesn’t it? Let us give you the logic of why method II is correct: Recall that division is nothing but grouping. When you divide n by 30, you make complete groups of 30 each. The number of groups you get is called the quotient (not relevant here) and the leftover is called the remainder. If this is not clear, check this post first. When n is divided by 30, groups of 30 are made. Whatever is leftover is given in the options. 30 is completely divisible by 6 and by 5 hence the groups of 30 can be evenly divided into groups of 6 as well as groups of 5. Now, whatever is leftover (given in the options) after division by 30, we need to split that into further groups of 6 and 5. When we split it into groups of 6 (i.e. divide the option by 6), we must have remainder 4 since n leaves remainder 4. When we split it into groups of 5 (i.e. divide the option by 5), we must have remainder 3 since n leaves remainder 3. And, that is the reason we can divide the options by 6 and 5, check their remainders and get the answer! Now, isn’t that neat!
_________________




Math Expert
Joined: 02 Sep 2009
Posts: 64275

Re: Divisibility and Remainders on the GMAT
[#permalink]
Show Tags
20 Oct 2015, 11:12
Divisibility Unraveled 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. Attachment:
Ques22.jpg [ 50.51 KiB  Viewed 41472 times ]
4 Attachment:
Ques31.jpg [ 14.58 KiB  Viewed 41192 times ]
Attachment:
Ques44.jpg [ 15.78 KiB  Viewed 41177 times ]
Attachment:
Ques5.jpg [ 16.73 KiB  Viewed 41148 times ]
_________________



Math Expert
Joined: 02 Sep 2009
Posts: 64275

Re: Divisibility and Remainders on the GMAT
[#permalink]
Show Tags
20 Oct 2015, 11:21
Divisibility Applied to Remainders 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. Attachment:
Ques31 (1).jpg [ 10.65 KiB  Viewed 41140 times ]
Attachment:
Ques4.jpg [ 16.77 KiB  Viewed 41146 times ]
Attachment:
Ques6.jpg [ 35.18 KiB  Viewed 41305 times ]
_________________



Math Expert
Joined: 02 Sep 2009
Posts: 64275

Re: Divisibility and Remainders on the GMAT
[#permalink]
Show Tags
20 Oct 2015, 11:28
Divisibility Applied to Remainders Part II 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.
_________________



Math Expert
Joined: 02 Sep 2009
Posts: 64275

Re: Divisibility and Remainders on the GMAT
[#permalink]
Show Tags
20 Oct 2015, 11:33
Knocking Off the Remaining Remainders 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 quotientremainder 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 quotientremainder 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 quotientremainder 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 quotientremainder 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!
_________________



Math Expert
Joined: 02 Sep 2009
Posts: 64275

Re: Divisibility and Remainders on the GMAT
[#permalink]
Show Tags
20 Oct 2015, 11:44
A Remainders Post for the Geek in You! 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^(n1)*b + n(n1)/2*a^(n2)*b^2 +……..+ n*a*b^(n1) + 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?”
_________________



Math Expert
Joined: 02 Sep 2009
Posts: 64275

Re: Divisibility and Remainders on the GMAT
[#permalink]
Show Tags
20 Oct 2015, 11:54
Successive Division We discussed divisibility and remainders. Here, we will use those concepts and discuss another type of question – successive division. What is meant by – ‘a number when divided successively by 4 and 5 leaves remainder 1 and 4 respectively’? Does it mean that when you divide the number by 4, the remainder is 1 and when you divide it by 5 the remainder is 4? No. It means that when you divide the number by 4, the remainder is 1 and then when you divide the quotient obtained (from the first division) by 5, the remainder is 4. e.g., when you divide 37 by 4, the remainder you get is 1 and the quotient you get is 9. When you divide 9 (not 37 here) by 5, the remainder you get is 4. This is what we mean by successive division i.e. you keep dividing quotients you get instead of starting with the original number again. Now that we understand what successive division is, let’s look at what kind of questions appear on successive division. Question 1: A number when divided successively by 4 and 5 leaves remainders 1 and 4 respectively. What will be the remainder when this number is divided by 20?(A) 0 (B) 3 (C) 4 (D) 9 (E) 17 Solution: Let’s find one number, say n, which when divided successively by 4 and 5 leaves remainder 1 and 4 respectively. When you divide n by 4, you get a quotient and remainder 1. When you divide the quotient by 5, you get the remainder 4. What can the quotient be (when you divide by 5) for the remainder to be 4? The first one that comes to mind is that the quotient could be 4 itself. If you divide 4 by 5, the remainder is 4. Now, if in the previous step when you divided n by 4, if the quotient was 4 and the remainder was 1, then the number n must have been 4*4 + 1 = 17 (n = Quotient*Divisor + Remainder). Now, what will be the remainder when you divide 17 by 20? It will be 17. Answer (E) This question is discussed HERE. Basically, you multiplied the second remainder with the first divisor and added the first remainder to get the first such number. Two divisors: 4, 5 Two remainders: 1, 4 Start from the bottom right corner and go up diagonally: 4*4. Then go down and add 1: 4*4 + 1 The first such number is 17. If you want to see the algebra approach, let us show you that too. n = 4a + 1 (When n is divided by 4, quotient is ‘a’) a = 5b + 4 (When a is divided by 5, quotient is ‘b’) n = 4(5b + 4) + 1 = 20b + 17 When n is divided by 20, we see that the remainder will be 17. The problem with the algebra approach is that it gets a little cumbersome when dealing with 3 or more successive divisions. Let’s look at a question involving 3 divisions now. Question 2: On dividing a certain number by 5, 7 and 8 successively, the remainders obtained are 2, 3 and 4 respectively. When the order of division is reversed and the number is successively divided by 8, 7 and 5, the respective remainders will be:(A) 3, 3, 2 (B) 3, 4, 2 (C) 5, 4, 3 (D) 5, 5, 2 (E) 6, 4, 3 Solution:Three given divisors: 5, 7, 8 Three given remainders: 2, 3, 4 We start by considering the last step first. At the end, when we divide by 8, we want remainder to be 4. This means that after division by 7, we should get 4 as the quotient (to get the first value of n). When we divide by 7, the quotient must be 4 and the remainder must be 3. At this step, the number becomes 7*4 + 3 = 31 Now, when we divide by 5, we need the quotient to be 31 and remainder to be 2 so number must be 5*31 + 2 = 157 157 is the first such number. Divide 157 by 8, 7 and 5, in that order: 157/8 gives quotient = 19 and remainder = 5 19/7 gives quotient = 2 and remainder = 5 2/5 gives quotient = 0 and remainder = 2 Remainders are 5, 5, 2 Answer (D) This question is discussed HERE. The steps followed are these: Three Divisors: 5, 7, 8 Three Remain: 2, 3, 4 Start from the bottom of the last column i.e. from the third remainder: Go up diagonally and multiply by the second divisor: 4*7 = 28 Go down and add the second remainder: 28 + 3 = 31 Go up diagonally and multiply by the first divisor: 31* 5 = 155 Go down and add the first remainder: 155 + 2 = 157 157 is the first such number. Now proceed as before to get the remainders when you divide 157 by 8, 7 and 5. Now you can tackle any number of divisors and remainders easily!
_________________



Math Expert
Joined: 02 Sep 2009
Posts: 64275

Re: Divisibility and Remainders on the GMAT
[#permalink]
Show Tags
20 Oct 2015, 12:00
All About Negative Remainders on the GMAT 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. Attachment:
Ques31 (2).jpg [ 10.65 KiB  Viewed 40981 times ]
_________________



Math Expert
Joined: 02 Sep 2009
Posts: 64275

Re: Divisibility and Remainders on the GMAT
[#permalink]
Show Tags
20 Oct 2015, 12:04
A Tricky Question on Negative Remainders 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?
_________________



Math Expert
Joined: 02 Sep 2009
Posts: 64275

Divisibility and Remainders on the GMAT
[#permalink]
Show Tags
20 Oct 2015, 12:23



Manager
Joined: 13 Sep 2015
Posts: 82
Location: United States
Concentration: Social Entrepreneurship, International Business
GPA: 3.84

Re: Divisibility and Remainders on the GMAT
[#permalink]
Show Tags
21 Oct 2015, 05:43
Bunuel wrote: A Remainders Shortcut for the GMAT We firmly believe that teaching someone is a most productive learning for oneself and every now and then, something happens that strengthens this belief of ours. It’s the questions people ask – knowingly or unknowingly – that connect strings in our mind such that we feel we have gained more from the discussion than even our students! The other day, we came across this common GMAT question on remainders and many people had solved it the way we would expect them to solve. One person, perhaps erroneously, used a shortcut which upon reflection made perfect sense. Let me give you that question and the shortcut and the problem with the shortcut. We would like you to reflect on why the shortcut actually does make sense and is worth noting down in your log book. Question: Positive integer n leaves a remainder of 4 after division by 6 and a remainder of 3 after division by 5. If n is greater than 30, what is the remainder that n leaves after division by 30?(A) 3 (B) 12 (C) 18 (D) 22 (E) 28 Solution: We are assuming you know how people do the question usually: The logic it uses is discussed here and the solution is given below as Method I. Method I:Positive integer n leaves a remainder of 4 after division by 6. So n = 6a + 4 n can take various values depending on the values of a (which can be any non negative integer). Some values n can take are: 4, 10, 16, 22, 28, … Positive integer n leaves a remainder of 3 after division by 5. So n = 5b + 3 n can take various values depending on the values of a (which can be any non negative integer). Some values n can take are: 3, 8, 13, 18, 23, 28, … The first common value is 28. So n = 30k + 28 Hence remainder when positive integer n is divided by 30 is 28. Answer: E. This question is discussed HERE. Perfect! But one fine gentleman came up with the following solution wondering whether he had made a mistake since it seemed to be “super simple Math”. Method II:Given in question: “n leaves a remainder of 4 after division by 6 and a remainder of 3 after division by 5.” Divide the options by 6 and 5. The one that gives a remainder of 4 and 3 respectively will be correct. (A) 3 / 6 gives Remainder = 3 > INCORRECT (B) 12 / 6 gives Remainder = 0 > INCORRECT (C) 18 / 6 gives Remainder = 0 > INCORRECT (D) 22 / 6 gives Remainder = 4 but 22 / 5 gives Remainder = 2 > INCORRECT (E) 28 / 6 gives Remainder = 4 and 28 / 5 gives Remainder = 3 > CORRECT Now let us point out that the options are not the values of n; they are the values of remainder that is leftover after you divide n by 30. The question says that n must give a remainder of 4 upon division by 6 and a remainder of 3 upon division by 5. This solution divided the options (which are not the values of n) by 6 and 5 and got the remainder as 4 and 3 respectively. So the premise that when you divide the correct option by 6 and 5, you should get a remainder of 4 and 3 respectively is faulty, right? This is where we want you to take a moment and think: Is this premise actually faulty? The fun part is that method II is perfectly correct too. Method I seems a little complicated when compared with Method II, doesn’t it? Let us give you the logic of why method II is correct: Recall that division is nothing but grouping. When you divide n by 30, you make complete groups of 30 each. The number of groups you get is called the quotient (not relevant here) and the leftover is called the remainder. If this is not clear, check this post first. When n is divided by 30, groups of 30 are made. Whatever is leftover is given in the options. 30 is completely divisible by 6 and by 5 hence the groups of 30 can be evenly divided into groups of 6 as well as groups of 5. Now, whatever is leftover (given in the options) after division by 30, we need to split that into further groups of 6 and 5. When we split it into groups of 6 (i.e. divide the option by 6), we must have remainder 4 since n leaves remainder 4. When we split it into groups of 5 (i.e. divide the option by 5), we must have remainder 3 since n leaves remainder 3. And, that is the reason we can divide the options by 6 and 5, check their remainders and get the answer! Now, isn’t that neat! 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=6n5n=30(ba)2 because n is an integer so ba could be any integer that makes n>0, so ba=c, whatever ba is doesn't affect the remainder: n=30c2 and because n>30, c>=2, so you n=30(c1)+302, like the result of ba doesn't affect the remainder, nor does c1 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



Intern
Joined: 29 Oct 2014
Posts: 34

Re: Divisibility and Remainders on the GMAT
[#permalink]
Show Tags
22 Oct 2015, 03:51
Bunuel wrote: Divisibility and Remainders on the GMATDivisibility Unraveled Today, I will start the topic of Divisibility. We will discuss what divisibility is at a very basic level this week and then move on to remainders in the coming weeks. So the first question is – what is division? Don’t tell me what to do to divide a number by another, tell me why you do it. What is it that you are achieving by dividing one number by another? Let me tell you what I think – I like to think that division is grouping. Not happy? Let’s look at an example then. When I divide 6 by 2, I am actually just making groups of 2 from 6 and subtracting them. 6 – 2 = 4 (One group of 2 subtracted.) 4 – 2 = 2 (Another group of 2 subtracted.) 2 – 2 = 0 (Third group of 2 subtracted.) I subtracted three groups so I get 3 as my quotient. Nothing is leftover so remainder is 0. If I were to divide 14 by 3, I would subtract 4 groups of 3 from 14 giving me a quotient of 4, and 2 will be leftover. Hence, remainder will be 2. Hopefully, this made sense to you. Now let’s look at division from the ‘divisibility angle’. Is 82 divisible by 4? What I mean to ask here is that can I subtract groups of 4 from 82 such that nothing is leftover? When I subtract 20 groups of 4 (=80) from 82, I am left with 2. I cannot make any more groups of 4. Since we have a remainder of 2, 82 is not divisible by 4. I have a fascination for diagrams. It stems in part from the fact that I wanted to be an artist but found that I have no talent in the field, and in part from the fact that I believe that diagrams help people understand the concepts better. On that note, let me draw a few diagrams to help you understand divisibility. Thereafter, you will be able to solve the tricky remainder questions quickly. Imagine numbers as balls. When I say 7, imagine 7 balls in a group. Let’s start easy: Is 7 divisible by 3? Before answering, think of the following figure: To divide by 3, I have to split 7 into groups of 3. I can make two groups of 3 and then 1 ball is leftover. Hence, when I divide 7 by 3, quotient is 2 and remainder, the ball that could not be put in a group, is 1. Similarly, what happens when I divide 12 by 3? I get 4 groups and nothing is leftover. (Is this then the diagrammatic representation of 12 = 3*4? Sure.) Then when I divide 12 by 4, I should be able to get 3 groups with nothing leftover. I guess you get the picture! Now, a question: I have a number that when divided by 6, leaves a remainder of 2. What will be the remainder when the number is divided by 3?(Do you think I moved on too quickly to too difficult a concept? Not really, just follow me) So here, I do not know what the number is, but I know that when I make groups of 6 balls each, 2 balls are leftover (as shown in the diagram below). Logically, it follows that when I split each group of 6 balls into two groups of 3 balls, I will still have the same 2 balls remaining. Since there are 2 balls leftover when groups of 3 are made, we can say that when we divide this number by 3, the remainder will still be 2! You don’t have to make the diagram in the exam of course. Just imagine it. A slight twist on the question above: I have a number that when divided by 6, leaves a remainder of 4. What will be the remainder when the number is divided by 3? Imagine the picture. Just like above but with groups of 6, there are 4 balls leftover. You divide the groups of 6 into groups of 3 – all is well till now – but then, you make another group of 3 from the 4 balls that are leftover. Therefore, only one ball will be leftover. Hence, when you divide the given number by 3, the remainder will be 1! Try a few more examples and let this theory sink in. We will delve into more details in the coming few weeks. Attachment: Ques.jpg Attachment: Ques (1).jpg Attachment: Ques (2).jpg Attachment: Ques (3).jpg Bunuel Hi. can you please post a small write up in which basic concepts of TIME RATE AND WORK problems are explained. THanks



Math Expert
Joined: 02 Sep 2009
Posts: 64275

Re: Divisibility and Remainders on the GMAT
[#permalink]
Show Tags
22 Oct 2015, 07:20
sharma123 wrote: 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: workrateproblemsallinonetopic205201.htmlOther important topics are here: view_important_topics.php?f=7&sk=t&sd=dHope it helps.
_________________



Math Expert
Joined: 02 Sep 2009
Posts: 64275

Re: Divisibility and Remainders on the GMAT
[#permalink]
Show Tags
04 Jul 2017, 12:11
Advanced Applications of Common Factors on the GMAT 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 (xm)?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 xm 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.
_________________



Math Expert
Joined: 02 Sep 2009
Posts: 64275

Re: Divisibility and Remainders on the GMAT
[#permalink]
Show Tags
31 Aug 2017, 22:16
Using Ingenuity on GMAT Remainder Questions 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.
_________________



Intern
Joined: 04 Sep 2017
Posts: 11

Re: Divisibility and Remainders on the GMAT
[#permalink]
Show Tags
05 Dec 2017, 22:24
This is an awesome thread. Kudos to you guys for your efforts!



VP
Joined: 09 Mar 2016
Posts: 1241

Re: Divisibility and Remainders on the GMAT
[#permalink]
Show Tags
06 Jun 2018, 09:18
Bunuel wrote: Divisibility Applied to Remainders 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. Attachment: Ques31 (1).jpg Attachment: Ques4.jpg Attachment: Ques6.jpg 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



Current Student
Joined: 24 Mar 2017
Posts: 148
Location: India
GMAT 1: 680 Q49 V34
GPA: 3.98

Re: Divisibility and Remainders on the GMAT
[#permalink]
Show Tags
06 Jun 2018, 11:27
dave13 wrote: Bunuel wrote: Divisibility Applied to Remainders 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. Attachment: Ques31 (1).jpg Attachment: Ques4.jpg Attachment: Ques6.jpg 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 dave13suppose we have n=7 this can be written as n=3k+1 where n = 7, k=2 also we can write n=3a2 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*34. Hope it helps.



VP
Joined: 09 Mar 2016
Posts: 1241

Divisibility and Remainders on the GMAT
[#permalink]
Show Tags
07 Jun 2018, 13:18
Bunuel wrote: Divisibility Applied to Remainders Part II 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. 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:)




Divisibility and Remainders on the GMAT
[#permalink]
07 Jun 2018, 13:18



Go to page
1 2
Next
[ 28 posts ]

