The Number of Divisors of an Integer

Date: 04/02/98 at 15:40:24
From: Simon Lloyd
Subject: Finding the total number of divisors, d(N), of any integer, N

Twenty-four has 8 divisors, namely 1,2,3,4,6,8,12 and 24. I have to 
find a relationship between the integer, N, and the total number of 
its divisors, d(N). I have found that every prime number will have 2 
divisors, every integer which is the square of a prime will have 3 
divisors, every integer which is a cube of a prime number will have 4 
divisors, etc. Building on this, I've also found that every number can 
be expressed uniquely as the product of primes and that there is a 
relationship between the exponents of the primes and d(N). For 
example,

     24 = 2^(3)*3^(1)

therefore, d(24) = (3 + 1)(1 + 1) = 8. 

However, I need to be able to prove this mathematically and explain 
why it is so, and this is where I'm having problems. I really hope you 
can help!

Date: 04/03/98 at 06:51:14
From: Doctor Anthony
Subject: Re: Finding the total number of divisors, d(N), of any 
integer, N

The reasoning you give is correct. You just need to show how it works 
in general.

If a number is a perfect square, it will have an odd number of factors 
(e.g., 4 has factors 1, 2, 4), whereas all other numbers have an even 
number of factors.

To show that square numbers always have an odd number of factors, 
consider a square, such as 36.

This can be put into prime factors as 2^2*3^2. Note that all its prime 
factors will be raised to EVEN powers since it is a perfect square.

Now, the factor 2 can be chosen in 3 ways, i.e., not at all, once, or 
twice.

And the factor 3 can also be chosen in 3 ways, i.e., not at all, once, 
or twice.

(If neither is chosen, we get the factor 2^0*3^0 = 1.)

All together, there will be 3*3 = 9 factors of 36. These are:

     1, 2, 3, 4, 6, 9, 12, 18, 36

Now, the important point was made earlier that the prime factors of a 
perfect square are always raised to some even power, so we could have 
 
     a^2*b^4*c^2,

where a, b, c are primes.

In this example:

     a could be chosen in 3 ways:  0, 1, 2 times
     b could be chosen in 5 ways:  0, 1, 2, 3, 4 times
     c could be chosen in 3 ways:  0, 1, 2 times

So, all together, the complete number will have 3*5*3 = 45 factors; 
and note that we are always multiplying odd numbers to get an odd 
number, 45 in this case.

For any number that is not a perfect square, there will ALWAYS be an 
even number of factors:

     a^3*b^2*c  will have   4*3*2 factors = 24 factors

If it is not a perfect square, at least one of its prime factors will 
be raised to an ODD power, and that means the factor can be chosen in 
an EVEN number of ways, ensuring that overall there will be an even 
number of factors.

The general rule for the number of factors is to increase the powers 
of the factors by 1 and multiply these together.

So:

     a^n*b^m*c^p  will have (n + 1)(m + 1)(p + 1) factors.

     2^3*5^4*7^2  will have 4*5*3 = 60 factors   

-Doctor Anthony, The Math Forum
Check out our web site! http://mathforum.org/dr.math/