The user-friendly version of this content is available here.

The following content is copyright (c) 2009-2013 by Goods of the Mind, LLC.

This essential trains for: SAT-I, AMC-8, AMC-10, Math Kangaroo 7-8, Math Kangaroo 9-10.

How many positive divisors does a positive integer have?

Let us assume an integer N. According to the fundamental theorem of arithmetic, it is either prime or composite.

If it is prime, then it has 2 positive divisors: 1 and itself - and this is the answer to the question.

If it is composite, then it has the unique prime factorization:

equation

where:

equation

are k prime numbers ordered increasingly (so as to make sure they are all different and all the multiple occurences of a given prime in the factorization have been accounted for by using integer exponents)

and:

equation

are k positive integer exponents that account for multiple occurences of each prime in the factorization. Note that no such exponent can be zero, since 1 is not a prime number; hence, it cannot be used in a factorization.

The question is: can we calculate how many distinct positive divisors N has?

If the number had only one prime in its factorization:

equation

then it would have the distinct positive divisors listed below:

equation

Notice that the number of divisors would be:

equation

since the exponents start at zero (1 is a valid divisor, though not a prime one).

Now if we had only two primes in the factorization:

equation

we would have (a2+1) divisors for each divisor that we had just with one prime:

equation

equation

equation

and up to:

equation

The total number of divisors would be:

equation

That is, unless there was any chance that any of the products listed coincide.

For instance, if there are i, j, k and t such that:

equation

But this is not possible since the prime factorization of any integer is unique. Therefore the left hand product cannot be equal to the right hand one unless the exponents are exactly the same and we have, therefore, the same product.

Thus, all the (a1+1)(a2+1) divisors are distinct.

Extending this reasoning to all the primes in the initial factorization, we obtain a formula for the number of distinct positive divisors of a positive integer:

equation

The notation is sort of standard.

Observe how the number of divisors of a number does not depend on the actual primes in the factorization, but only on the exponents they come at.

Therefore, if two numbers have the same number of primes in their factorization and the same set of exponents, they also have the same number of positive divisors. For example:

equation

Having the number of divisors of a number does not give us the number, but does give us an idea of what the prime factorization of it looks like.

Example: If a number has 12 divisors then we can make some assumptions about its prime factorization as follows:

equation

equation

equation

equation

Conclusion 1: the unknown number may have one, two or three primes in its factorization.

Conclusion 2: the prime factorization of the unknown number may have one of the following four forms:

equation

equation

equation

equation

Property: the number of divisors is multiplicative. The number of divisors of a product of numbers is equal to the product of the numbers of divisors of each number:

equation

Note: A perfect square has an odd number of positive divisors.

Take any integer and write the prime factorization:

equation

Square both sides:

equation

and calculate the number of divisors:

equation

It is obvious that, being a product of odd numbers, it is also odd.