GMAT Math

To recap the 'trick' discussed above, if you want to count how many different positive divisors a number n has, you can:

-prime factorize n, writing the prime factorization using powers
-look only at the exponents in the prime factorization
-add one to each exponent, and multiply the resulting numbers together

So the number 144 = (2^4)*(3^2) has (4+1)*(2+1) = 15 divisors in total, for example.

_____________

There are a few ways to see why you can use this 'trick' to count the divisors of a number. Take, for example, the number 6125. Prime factorizing this number, we find it's equal to (5^3)*(7^2). According to the 'trick', this number should have 12 divisors. Well, what are the divisors of (5^3)*(7^2)? It's divisible by each power of 5 up to 5^3:

1, 5, 5^2, 5^3

We can also multiply each number in the list above by 7 to get another set of four divisors:

7, 5*7, (5^2)*7, (5^3)*7

and we can multiply each number in our first list by 7^2 to get yet another set of four divisors:

7^2, 5*(7^2), (5^2)*(7^2), (5^3)*(7^2)

Those are the only combinations of 5's and 7's for which the exponent on the 5 is three or less, and the exponent on the 7 is two or less, so we have listed all 12 divisors of 6125.

From the above, you might be able to see why the 'trick' works; to make a divisor of (5^3)*(7^2), we can choose to have zero, one, two or three 5's, and zero, one or two 7's. That is, we have four choices for the number of 5's, and three choices for the number of 7's, and therefore 4*3 = 12 choices in total.

The more abstract proof: suppose

x = (p^5)*(q^3)

is a prime factorization (i.e. p and q are different primes). Any number

d = (p^a)*(q^b)

will be a divisor of x as long as the powers in d are less than or equal to the powers in x. That is, d will be a divisor of x provided that:

a = 0, 1, 2, 3, 4 or 5

and

b = 0, 1, 2 or 3

So we have six choices for a, and four choices for b, and therefore 6*4 = 24 choices in total for the powers a and b, and therefore 24 different divisors of x. That is, we add one to each power in the prime factorization and multiply.

I've used numbers for the powers here for clarity, and a prime factorization with only two prime factors, but this of course works no matter how many primes you have, and no matter what the powers.