The Importance of Prime Factorization on the GMAT

by , Mar 3, 2010

Rich Zwelling is a stellar teacher in Knewton's GMAT course. And its not just shtick: He really does love prime factorization.

Prime Factorization: My single favorite topic on the GMAT. Hands down.

My passionate (some would say evangelical!) advocacy of prime factorization results not only from my finding prime numbers so intrinsically fascinating in and of themselves, but also from the plain and simple truth that prime factorization proves surprisingly useful on questions on which prime numbers aren't even mentioned.

For example, any time you're given a question asking about multiples and factors, you can bet that prime factorization will help you get to the answer quicker.

Check out this Data Sufficiency question from the Official GMAT Guide:

If positive integer x is a multiple of 6 and positive integer y is a multiple of 14, is xy a multiple of 105?

(1) x is a multiple of 9

(2) x is a multiple of 25

Note that there is no mention of prime numbers at all. But take any other approach to this problem, and you're likely to get pretty frustrated and lost rather quickly. You could certainly test numbers, but good luck taking only two minutes finding values that work for every case!

Now, I'm going to re-write the question and statements using only prime factorizations:

If positive integer x is a multiple of 2*3 and positive integer y is a multiple of 2*7, is xy a multiple of 3*5*7?

(1) x is a multiple of 3*3

(2) x is a multiple of 5*5

All of a sudden, the question becomes much more manageable. We know that x carries at least one 2 and one 3 as factors. We also know that y carries at least one 2 and one 7 as factors. Therefore, the product xy must carry at least two 2s, one 3, and one 7.

We are asked if xy carries at least one 3, one 5, and one 7 as factors. So far, we know we xy has one 3 and one 7, so all that's missing is the one 5. What we've just done is show that in order to establish sufficiency, all we need to do is determine whether there's a factor of 5 somewhere in x or y (or both).

Statement 1 lets us know that x has two 3s and mentions nothing of 5s. But that doesn't necessarily mean there isn't a 5 there. There also might be a factor of 5 in y. Because we cannot determine the presence or absence of factors of 5, this statement is insufficient.

Statement 2, on the other hand, lets us know that x definitely has a factor of 5. And again, we already know from the prompt that x has a factor of 3 and y has a factor of 7. Therefore, the product xy has at least one 3, one 5, and one 7 as factors, and we can conclude unequivocally that xy is a multiple of 3*5*7 = 105. Sufficient.

Final answer: B

Even on questions that do explicitly mention prime numbers, things can get really ugly really quickly if you don't use prime factorization.

For example, take this Problem Solving question, also from the Official Guide (answer choices not included):

In a certain game, a large container is filled with red, yellow, green, and blue beads worth, respectively, 7, 5, 3, and 2 points each. A number of beads are then removed from the container. If the product of the point values of the removed beads is 147,000, how many red beads were removed?

The use of 2, 3, 5, and 7 is a prime clue (pun indeed intended). You might look at 147,000 and panic because the number is so large. But let's break down 147,000 into its prime factorization:

147,000

= 147 * 1000

= (7 * 21) * 10 * 10 * 10

= (7 * 7 * 3) * (2*5) * (2*5) * (2*5)

Now, the question asks us how many red beads were removed. Red beads are associated with a point value of 7.

We know that the final point total was 147,000, and when we broke that number down, we found that there were only two factors of 7. Therefore, the only way we could get that score is if we removed 2 red beads. That's it! 2 is our final answer!

These are just two examples of a large number of questions made easier by prime-factor prowess. Practice making those factor trees! And notice how prime numbers help you answer questions about other topics like Greatest Common Factor and Least Common Multiple.