Pesky Prime Theory
Data Sufficiency problems often have elegant shortcuts if we really understand the theory behind whatever the problem tests and, sometimes, DS sets up some very tricky traps if we really dont understand the theory. Lets try one out.
This problem is from GMATPrep. Set your timer for 2 minutes. and GO!
* If r and s are positive integers, is r/s an integer?(1) Every factor of s is also a factor of r.
(2) Every prime factor of s is also a prime factor of r.
How did it go? The question stem seems pretty straightforward. They tell us that r and s are positive integers and they ask a (seemingly!) simple question: is r/s an integer?
What does that question really mean? What would need to be true in order for r/s to be an integer? What would need to be true for it NOT to be an integer?
When dividing, were going to get an integer only if the denominator, in this case s, divides evenly into the numerator, in this case r. The denominator has to go away completely. For example, 6/3 is an integer, because the 3 "goes away" or divides out completely, but 7/3 is not. Whats this really asking, then? Its a factor question in disguise! If s is a factor of r, then the resulting number will be an integer. If, on the other hand, s is not a factor of r, then the resulting number will not be an integer.
Now, you might pick up that idea when you look at the statements, since both mention some form of factors. But try to get in the habit of noticing right away that, when they ask whether dividing one thing into another will produce an integer, theyre really asking whether one thing is a factor of another thing.
Okay, so theyre really asking whether s is a factor of r. You could also word it as: is r a multiple of s? Lets examine statement 1:
(1) Every factor of s is also a factor of r.
Well, this seems to be exactly what we were talking about a minute ago, doesnt it? So this one should be sufficient. And, hey, statement 2 seems to be saying the same thing, right? So I guess I can just pick D and move on.
Slow down a little. Maybe thats how the problem will play out, but lets examine this a little more carefully to make sure we dont make a mistake.
First, an important note. The shared numbers are what Ill call unidirectional. That is, r contains all of ss factors, but s does NOT necessarily contain all of rs factors. Theyre not saying that r and s each have the same factors as the other. (The same is true for statement 2, except substitute prime factors for factors in the preceding sentences.)
So, we have an s. According to statement 1, every single one of ss factors also shows up as a factor of r. If s is 12, for example, then ss factors are 1, 2, 3, 4, 6, and 12, and r would contain all of those same factors. If s is 15, then ss factors are 1, 3, 5, and 15, and r would contain all of those same factors. Notice any useful patterns here?
Heres where theory comes in. Recall the idea that, in order to get an integer when dividing, the denominator has to go away or cancel out completely. If s is 12, then one of its factors is 12 because, by definition, any number has itself as a factor. 15 is a factor of 15, 4 is a factor of 4, 23 is a factor of 23. Statement 1 tells us that r contains all of ss factors. Because one of ss factors is always itself, that means r actually contains s s is a factor of r and r is a multiple of s, and so we can always divide out s from the top and the bottom of the fraction.
So, if youve trained yourself to know that is r/s an integer is really just asking whether s is a factor of r, and if you know that factor theory tells us that s would have to divide out completely, then you know the key to the question is this: does r completely contain all of the factors of s, or does r contain s itself? And, if you know that, then you can evaluate statement 1 very quickly: whatever the value of s, that value is itself a factor of r, so s will divide out completely. In other words, yes, r/s is an integer. Youve just used theory to solve statement 1!
Cross off answers B, C, and E and move on to statement 2:
(2) Every prime factor of s is also a prime factor of r.
All right, now we said that this is just the same as statement 1, right? Well, lets see. If s is 6, then the prime factors are 2 and 3. The r variable would also need to contain that 2 and 3, and so the entire 6 would divide out completely for r/s, and wed be left with an integer.
What if s is 8? Now, s has only 2 as a prime factor. And r contains oh, wait, heres an interesting question. Does r contain just one 2? Or does r contain three 2s? Read the statement again. What do you think?
The statement talks about every prime factor of s. If s = 8, what is every prime factor? The number 8 has just one prime factor: 2. That prime factor is used, or repeated, three times, but it is still just the same factor 2. So the only requirement here is that r contain a 2. Now, r could be 16, in which case r/s = 16/8 = still an integer. But what if r is, say, 10? Does r contain whatever prime factor or factors are contained in s?
It does. We found that s contains the prime factor 2, so r must also have the prime factor 2, and it does. But note that s(8) actually contains that prime factor three times, while r(10) contains the prime factor 2 only once. The result? r/s = 10/8 = NOT an integer. This statement is NOT sufficient and the correct answer is A.
See what they did to us here? Its not an accident that the two statements came in this particular order. We test statement 1 first because, well, they gave it to us first. And, once we do that, were predisposed to think, Oh, well, if they have the same factors, then yeah, Im going to get an integer, even if were talking about prime factors instead. Factors are factors. But saying that one number contains all of another numbers regular factors is very different than saying that one number contains allof another numbers prime factors. In the latter case, youd have to specify that the repeats are all included that, if we have three 2s in s, then we also have three 2s in r. Statement 2, though, doesnt do that.
What are your takeaways from this problem? Figure them out before you keep reading.
Key Takeaways for Factor Theory Problems
(1) Asking whether a certain division calculation will result in an integer is a disguise. Theyre really asking whether one thing is a factor of another.
(2) If one variable (lets call it x) contains all of the same factors as another variable (call this one y), then by definition, x is a multiple of y. This always works because y itself is always a factor of y, so if x contains y as a factor, then x is a multiple of y. Heres that idea again using real numbers as an example. If 32 contains all of the same factors as 8 including 8 itself, then by definition, 32 is a multiple of 8, because 32 contains 8 itself as a factor.
(3) If one variable (lets call it a) contains the same basic prime factors as another variable (call this one b), then we dont know whether a is a multiple of b. Its possible, such as when a = 12 and b = 6; b has 2 and 3 as prime factors, and a shares that characteristic. In this case, 12 is a multiple of 6. On the other hand, if a = 30 and b = 12, then b has 2 and 3 as prime factors, and a shares that characteristic, but now, 30 is not a multiple of 12. This is because b actually contains two 2s, but 30 contains only one 2.
* GMATPrep questions courtesy of the Graduate Management Admissions Council. Usage of this question does not imply endorsement by GMAC.