# Pesky Prime Theory

by on November 9th, 2012

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 don’t understand the theory. Let’s 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, we’re 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. What’s this really asking, then? It’s 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, they’re really asking whether one thing is a factor of another thing.

Okay, so they’re really asking whether s is a factor of r. You could also word it as: is r a multiple of s? Let’s 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, doesn’t 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 that’s how the problem will play out, but let’s examine this a little more carefully to make sure we don’t make a mistake.

First, an important note. The shared numbers are what I’ll call “unidirectional.” That is, r contains all of s’s factors, but s does NOT necessarily contain all of r’s factors. They’re 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 s’s factors also shows up as a factor of r. If s is 12, for example, then s’s factors are 1, 2, 3, 4, 6, and 12, and r would contain all of those same factors. If s is 15, then s’s factors are 1, 3, 5, and 15, and r would contain all of those same factors. Notice any useful patterns here?

Here’s 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 s’s factors.  Because one of s’s factors is always itself, that means r actually contains ss 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 you’ve 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. You’ve 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, let’s 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 we’d be left with an integer.

What if s is 8? Now, s has only 2 as a prime factor. And r contains… oh, wait, here’s 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? It’s 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, we’re predisposed to think, “Oh, well, if they have the same factors, then yeah, I’m going to get an integer, even if we’re talking about prime factors instead. Factors are factors.” But saying that one number contains all of another number’s regular factors is very different than saying that one number contains all of another number’s prime factors. In the latter case, you’d 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, doesn’t 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. They’re really asking whether one thing is a factor of another.

(2) If one variable (let’s 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. Here’s 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 (let’s call it a) contains the same basic prime factors as another variable (call this one b), then we don’t know whether a is a multiple of b. It’s 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.