Divide and Conquer: The Hidden Tactic
 |
Aaron is a Master GMAT expert. Click here to learn more about The Economist GMAT Tutor and its products & services. |
A solid knowledge of number properties is generally not enough for handling the most advanced factorization problems on the Quant. Although most students can handle the simple task of finding the prime factorization of a number, only rarely will you see a question phrased so bluntly. More likely, the question will only hint at the issue in a roundabout fashion:
If x, y and z are positive integers, is it true that
is divisible by 16?
There’s not a word mentioning prime factorization, yet clearly this is the issue being tested. Two hints clue us to this fact:
- The test for divisibility involves variables, but no remainder is mentioned
- All (or many) of the variables in the problem are limited to integers
The presence of these two clues together often suggest that you should divide and conquer. Much like the military tactic, mathematical division can help break a complex problem into smaller, bite-sized chunks that are easier to handle.
The difficulty here is that each statement involves two variables that we need to juggle in our heads. Clearly, it would be far simpler if we only had to consider one variable at a time. Let’s divide and conquer so we can do just that, starting with statement 1):
Divide both sides by 4 to get:
The right-side of the equation is an integer since y is an integer. so logically, the left-side of the equation must be an integer, too. If we now focus only on the left-side of the equation, we only need to concern ourselves with a single expression with a single variable: 5x/4.
In order for 5x/4 to be an integer, all of the prime factors in the denominator (two 2′s) must also be present in the numerator (which contains 5 and x). This must be true in order for 5x/4 to be an integer. Because the 5 in the numerator does not contain any factors of 2, x must contain at least two factors of 2. , then, must contain at least four factors of 2. In other words, must also divisible by 16. The answer to the question stem is therefore a definite Yes.
Statement 2) can be conquered using the same tactic:
Divide both sides by 8 to obtain
Using the same logic, we see that 
must contain at least three factors of 2. Since 3 obviously won’t contain any factors of 2, they must all come from the term.
At first glance, it may seem like we have insufficient data, since we have only been able to prove that has at least three factors of 2 rather than four. Notice, however, that since 
itself is an integer, must be a perfect square.
A perfect square must contain an even number of each prime factor. As an example, consider the perfect squares 4 (two factors of 2), 81 (four factors of 3), and 400 (four factors of 2, two factors of 5). If contained only three factors of 2, such as if = 8, it would no longer be a perfect square. If we were to take √(), we would end up with x = √8 = 2.82, which is not an integer. As a result, must always contain an even number of factors, or a minimum of at least four factors of 2. Once again, we have a definite Yes answer to the question stem. The answer to this data sufficiency question is therefore D): each statement alone is sufficient.
When dealing with these hidden factorization problems, remember the following divide and conquer tactic:
- Identify a single variable that must be an integer; isolate that variable on one side of the equation
- Focus on the complicated expression on the other side of the equation; it must also be an integer
- Figure out what prime factors must be present in the variables; the numerator must contain at least the same number of prime factors as the denominator
- If the expression involves a perfect square, go back to revise the number of prime factors so that there are an even number for each factor. Perfect cubes will have factors that come in triplets, and so on.
Now that you’ve learned the divide and conquer technique, try out this challenge problem:
If x is a prime number greater than 5, y is a positive integer, and
, then y must be divisible by which of the following?
- 5
- 2x
- x+1
(Note: more than one statement can be true)
13 comments
Ravisankar Vemuri on April 28th, 2012 at 3:37 am
A nice illustration
Ravisankar Vemuri on April 28th, 2012 at 4:00 am
Answer for the challenge problem is option II only.
y = (x^2+x)/5 = x(x+1)/5
x is a prime greater than 5. Here x can take only 19,29,59,... such that (x+1) can be divisible by 5 (the denominator). So each time at least a two will remain after the division of (x+1) with 5 and so 2x must definitely be one factor of y.
rishi on May 2nd, 2012 at 1:17 pm
but why not option 3..........can u please illustrate .........i think both 2 & 3 are correct
Mrudang on April 28th, 2012 at 11:06 am
Nice example... the answer to the question is
1. As 5 is in denominator... and y is an interger (I) is answer.
2. Asx are prime above 5 and to y to be divisible by 5 we have to select x such that x+1 is divisible by 5, such as 19, 29. Dividing x+1 by 5 will have 2. So 2x will also be factor.
ANS. (1) and (II)
mangal bajracharya on July 5th, 2012 at 10:20 pm
As y is the integer which is to be factorized in terms of 5
……….{*}, as x is prime greater than 5 , x can be 7,11,13,17,19,23,29,31,37…. but x can’t hold good for values 7,11,17,19,23,31..which don’t satisfy {*} ie they don’t form integers divisible by 5 ,
Those may be 19,29,59,79…….which end with unit digit 9.
If x = 19 , y = 19 * 4
If x = 29 , y = 29 * 6
If x = 59 , y = 59 * 12
If x = 79 , y = 79 * 16
Anywhere in factors of y, 5 doesn’t seem , so y can never be divisible by 5 .
That’s (I) is not true
Im so grateful to http://www.beatthegmat.com team for introducing me with many innovative ideas of maths
mangal bajracharya on July 5th, 2012 at 10:25 pm
CORRECTION OF OMMISSION,
y = x (x+1)/5 .........(*) ,
Sagar on April 29th, 2012 at 8:22 pm
I won't be an option because 5 is on the LHS. We need 5 on the RHS for y to be a multiple of 5. Correct answer is II.
ritz on April 30th, 2012 at 2:23 am
considering the RHS of
y = x(x+1) / 5
If y is +ve integer, x(x+1) should be divisible by 5.
Also, x is prime number greater than 5, hence x+1 should be a multiple of 5.
Going by which only option is II holds good.
Stoycho on May 1st, 2012 at 1:43 pm
Aaron, what is the correct answer? I feel like I, II and III all are correct? 5y = x^2 + x => 5y = x(x + 1) => y = x(x+1)/5; since y is an integer it must be divisible by 5 (I); all primes greater than 2 are odds (I believe), therefore "(x+1)" will always be even, therefore (II); we have "(x+1)" in enumerator => (III) works, too.
Stoycho on May 1st, 2012 at 1:50 pm
i take back #1 since that is conditional and does not cover all cases.
Master GMAT on May 6th, 2012 at 10:12 pm
The answer here is that only statement II) alone must be true. Congrats to all those who got it correct!
Brand Chen on May 14th, 2013 at 9:30 pm
http://gmatclub.com/forum/if-x-is-a-prime-number-greater-than-5-y-is-a-positive-141328.html
Brand Chen on May 14th, 2013 at 10:01 pm
If you interested why II must be true consider this: since x is a prime number greater than 5, then it's odd --> 5y=x(x+1)=odd(odd+1)=odd*even=even --> 5y=even --> y=even.
only even prime is 2, other than that, there are all odd