Divisors

Date: 11/07/97 at 20:25:07
From: Ryan
Subject: Figuring out how many divisors a number has

Hello. I am totally stumped on the following question:

Find a method to figuring out how many divisors a number has, and 
investigate the following:

 - what kinds of numbers have exactly 3 divisors?
 - do bigger numbers necessarily have more divisors? (I already know 
   the answer to this is no.)
 - Is there a way to figure out how many divisors 1,000,000 has 
   without actually listing and counting them?  How about 
   1,000,000,000?
 - What's the smallest number with 20 divisors?

If you could possibly give me a little help to get started on this (or 
an actual answer to one part or another : ) I would appreciate it a 
lot.  Thank you,
Ryan

Date: 11/08/97 at 08:38:19
From: Doctor Anthony
Subject: Re: Figuring out how many divisors a number has

To find the number of divisors you must first express the number in 
its prime factors. 

Example:  How many divisors are there of the number 12?

  12 = 2^2 x 3

The number 2 can be chosen 0 times, 1 time, 2 times = 3 ways.
The number 3 can be chosen 0 times, 1 time = 2 ways.

Putting these results together we have 3 x 2 = 6 ways of finding 
factors of 12.

Note that we add 1 to the power of the prime factor to see in how many 
ways that factor can be used, so if N = a^p x b^q x c^r, the total 
number of factors will be (p+1)(q+1)(r+1).

Let us check the answer 6 factors for the number 12 that we found 
earlier.

Factors are  1, 2, 3, 4, 6, 12 = 6 factors.

Note that our method of calculating number of factors will always 
include the number 1 and also the number itself.

Every number will have an even number of factors unless it is a 
perfect square, since if a prime factor is to power 1 or any odd 
power, it could be used in 2 or 4 or 6 ways - we must always include 
it being used 0 times.

But  9 = 3^2   so 3 could be used 0 times, 1 time, 2 times = 3 ways.

The smallest number with 20 factors requires you to find the way of 
reaching 20 as (p+1)(q+1)(r+1) .... = 20

20 factors,  so   N = 2^4 x 3^3 is a possibility, giving 5 x 4 factors  

another is        N = 2^4 x 3 x 5   giving 5 x 2 x 2  factors

The second is a smaller number so the answer is  240.

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

Date: 09/28/2002 at 15:21:51
From: Aaron 
Subject: How do you find the number of divisors without counting them?

Hello.  

I can't make any sense of this, where it says:

The number 2 can be chosen 0 times, 1 time, 2 times = 3 ways.
The number 3 can be chosen 0 times, 1 time = 2 ways.

What does that mean?  

Thanks, I appeciate it.

Date: 09/28/2002 at 21:26:01
From: Doctor Fenton
Subject: Re: How do you find the number of divisors without counting 
them?

Hi Aaron,

Thanks for writing to Dr. Math.  In your example of 12 = 2^2 * 3^1, 
any divisor of 12 must have only the prime factors 2 or 3, and it 
cannot have more than 2 factors of 2, or 1 factor of 3. So any divisor 
of 12 must have the form

    2^p*3^q, where p is 0,1, or 3, and q is 0 or 1.

You can create all divisors of 12 by (1) choosing a value for p, for 
which you have three choices; and then (2) choosing a value for q, for 
which you have two choices.

You choice of q does not depend on the choice you made for p, so for 
EACH of the three possible choices for p, there are 2 possible choices 
for q, for a total of 2*3=6 choices total. That's a combinatorial 
principle: if you must make k choices independently (no choice affects 
the options for later choices), and if the first choice can be made in
n(1) ways, the second choice in n(2) ways,... and the k-th choice in 
n(k) ways, then the total number of choices is

   n(1)*n(2)*...*n(k) .

[This is often called the Multiplication Principle.]

You can draw a tree diagram:
     
        p choice   q choice
                  q=0
                /               
             p=0 
            /   \ q=1   
           /
          /       q=0
         /      /
   start ----p=1
         \      \
          \       q=1
           \
            \   / q=0
             p=2
                \ q=1  .

This tree has 3 branches at the first level, and on each branch, there 
are two branches at the second level, so there are 3*2 branches in 
all.

Does this answer your question?  If you have further questions, please 
write back and I'll try to answer them.

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