Lesson: Counting the Divisors of Large Numbers

Rate this video: 

Comment on Counting the Divisors of Large Numbers

great tip! thank you so much!!

Should we consider 1 as the divisor of a number ?
gmat-admin's picture

1 is a divisor of all positive integers. However, with respect to the technique described in this video, we wouldn't include 1 in the prime factorization of the number for which we're trying to find the total number of divisors.

For example, to determine the total number of divisors of 14000, we first prime factorize 14000 to get 14000 = (2^4)(5^3)(7^1)

We wouldn't write: 14000 = (1^1)(2^4)(5^3)(7^1)

We wouldn't do this because 1 is NOT a prime number, so it has no place in the PRIME factorization of a number.

Also, including 1 would be problematic, because the exponent could be ANY number.

For example, 12 = (1^1)(2^2)(3^1) or 12 = (1^4)(2^2)(3^1) or 12 = (1^33)(2^2)(3^1) etc.

Does that help?

What is the rationale behind adding 1 to each exponent/ raising each prime factor to 0?
gmat-admin's picture

I cover this a 1:50 in the video.

We add 1, because we must also consider the possibility that the exponent is 0.

So, for example, if 2^5 is in the prime factorization of N, then when it comes to possible divisors of N, we must consider 2^5, 2^4, 2^3, 2^2, 2^1 and 2^0.
So there are 5+1 possible exponents.

I got 30 positive divisors for 1008, but I cant seem to get the other two right. Can you show me how you got 16 divisors for 3375, and 49 for 100 000?

I got 20 for 3375 and 36 for 100 000. Where am I going wrong? Hmm.
gmat-admin's picture

3375 = (3)(3)(3)(5)(5)(5) = (3^3)(5^3)
So, the number of divisors = (3+1)(3+1) = 16

1,000,000 = (2)(2)(2)(2)(2)(2)(5)(5)(5)(5)(5)(5) = (2^6)(5^6)
So, the number of divisors = (6+1)(6+1) = 49

Does that help?


Add a comment

Tweet about our course!

If you're enjoying our video course, help spread the word on Twitter.

Learning Guide

Our step-by-step Learning Guide will help direct your studies and ensure that you cover everything that the GMAT tests.

Have a question about this video?

Post your question in the Comment section below, and we’ll answer it as fast as humanly possible.