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:
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)
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:
then it would have the distinct positive divisors listed below:
Notice that the number of divisors would be:
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:
we would have
and up to:
The total number of divisors would be:
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:
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
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:
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:
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:
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:
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:
Note: A perfect square has an odd number of positive divisors.
Take any integer and write the prime factorization:
Square both sides:
and calculate the number of divisors:
It is obvious that, being a product of odd numbers, it is also odd.