The Knewton Blog

GMAT News 6/25/10: GMAC announces new GMAT section Integrated Reasoning.

Rich Zwelling is one of the expert teachers of Knewton’s GMAT course. He’s never been shy about professing his love for prime numbers.

If you’re knee-deep in your GMAT prep (or still remember some of your math from high school), chances are you’re already familiar with the “factor rainbow” method of listing any number’s given factors. For example, if we were to list all the factors of 60, we would match 1 with 60, then 2 with 30, then 3 with 20, etc.

If you need to know specific factors for a problem, this is the way to go. But if you’re only interested in finding HOW MANY factors the number has, it can get a bit tedious.

Lucky for you, there’s an easier way. Once again, prime numbers come to the rescue! (Are you starting to understand my evangelical passion for prime numbers?)

Believe it or not, there’s a way you can find the number of factors of ANY given number without even looking at any of the factors themselves.

Here’s how you do it.

Let’s say the number we’re interested in is 2,940. First step: Find the number’s prime factorization:

2940

10 * 294

(2*5) * (2*147)

(2*5) * (2*7*21)

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

Prime factorization: 2^2 * 3^1 * 5^1 * 7^2

For those who just want to know the strategy and don’t care about how or why it works, I’ll cut to the chase:

Our prime factorization was 2^2 * 3^1 * 5^1 * 7^2. In order to find the number of factors, all we need to do is add 1 to each exponent and multiply the results:

(2+1)*(1+1)*(1+1)*(2+1) = 3*2*2*3 = 36.

2,940 has a total of 36 factors. That’s it!

Now, for any curious and intrepid mathletes out there, let’s get into the nitty-gritty of exactly why this method works:

If we take the product of ANY combination of these prime factors, we will get a factor of the original value (2,940). For example, we could take both 2s, one 3, and one 7, and we can multiply them together to get 2*2*3*7 = 84, which is a factor of 2,940.

As a result, we can treat this like a combinations problem. We have to consider ALL possible combinations of the prime factors in order to get ALL possible factors of 2,940.

We have 2^2 in our prime factorization, but the tricky thing is that we actually have THREE powers of 2 to consider, namely 2^0, 2^1 and 2^2. This is because 2^0*3^1*5^1, for example, is a factor of 2,940. We have to remember that there might be no factors of 2.

So, 2^2 yields three possible powers of two.

We have 3^1 and 5^1. For each of those, two powers are involved (3^0 and 3^1, and also 5^0 and 5^1).

Finally, we have three for 7^2, namely 7^0, 7^1, and 7^2.

So, we can set up a visual representation of possible combinations that yield a factor of 2,940:

2^_ * 3^_ * 5^_ * 7^_ (where each blank represents a possible exponent).

There are 3 possible exponents for the first blank, 2 for the second, 2 for the third, and 3 for the fourth.

Total number of factors: 3*2*2*3 = 36.

And once again, the big takeaway:

Our prime factorization was 2^2 * 3^1 * 5^1 * 7^2. All we need to do is add 1 to each exponent and multiply the results:

(2+1)*(1+1)*(1+1)*(2+1) = 3*2*2*3 = 36.

2,940 has a total of 36 factors.

It may take a minute (or twenty!) to wrap your head around the logic behind this method, but once you apply it, you’ll find there’s no better strategy. It’s quick, accurate, and not very labor-intensive. It certainly beats writing out every factor!

Let’s try another one, so you can see how quick this can be:

540

5 * 108

5 * 2 * 54

5 * 2 * 2 * 27

5 * 2 * 2 * 3 * 3 * 3

Prime factorization: 2^2 * 3^3 * 5^1

Number of factors: (2+1)*(3+1)*(1+1) = 3*4*2 = 24.

540 has 24 factors.

Now, apply what we’ve done (and more!) to some thought exercises:

1. Try this method with perfect squares. Notice anything distinctive?

2. What type of number has exactly three factors? How about five?

3. How many numbers from 1 to 200 inclusive have no more than three distinct prime factors? (For example, 2^6 has only one distinct prime factor, namely 2.)

4. If you randomly pick a number from 1 to 100 inclusive, what is the probability that you choose a number that has exactly six factors?

Posted in GMAT, GMAT Tips, Quant Guide | 2 comments