Divisor Counting

Date: 9/24/95 at 23:49:12
From: Kelly Yu
Subject: Divisor Counting

   Problem of the Week:   Divisor Counting
   
   You may already know that a prime number is a whole number 
   which has exactly two whole number divisors, 1 and itself.   
   For example, 7 is a prime, since it has exactly two whole 
   number divisors, namely 1 and 7.
   
   On the other hand, 10 is not a prime, since it has four 
   whole number divisors, namely, 1, 2, 5, and 10.  
   
   The goal is for you to figure out more about how many 
divisors a number has.  The concept of prime number may be 
useful in stating your conclusions.
   
   Here are some questions to look at:
   
   1) What kinds of numbers have exactly 3 divisors?  exactly  
      4? etc.
   2) Do bigger numbers necessarily have more divisors?
   3) Is there a way to figure out how many divisors 1,000,000 
      (one million) has without actually listing and counting 
      them? How about 1,000,000,000 (one billion)?
   4) What's the smallest number that has 20 divisors?
   
   These are examples of questions to ask yourself.  But you 
should not stop at answering these questions or ones like them.  
You should come up with your own questions and find rules for 
different kinds of numbers.

P.S.  I've read some of the things on your homepage.  But, I 
feel that this problem is different since it is talking about 
divisors, not just primes.  I'm only a 14 year old sophomore, 
so I don't really understand some of those formulas like log, 
so please explain any formula you give.  I also want to know 
how you could determine if a number is a prime.  

                                  Sincerely yours,
                                  Kelly Yu

Date: 9/25/95 at 11:55:14
From: Doctor Ken
Subject: Re: Divisor Counting

Hello!

I remember when someone showed me how to count all the divisors 
of a number without having to list them all and count them up.  
I thought it was so darn cool.  I still do.  I think I was 
shown it when I was a sophomore in high school too, so you'll 
be able to understand just fine if I describe it correctly.

Let's think about how a number gets to be a divisor of another 
number.  If a divides b, then all the factors of a are also 
factors of b, right?  For example, 6 divides 24, because 6 = 
2 * 3, and 24 = 2^3 * 3, so all the divisors of 6 are present 
in the divisors of 24.  In another example, 14 doesn't divide 
50 because 14 = 2 * 7, and 50 = 2 * 5^2, and there's no 7 in 
50.

So we want to figure out all the different numbers we can make 
out of the factors of the given number.  For example, let's 
find all the divisors of 60: 60 = 2^2 * 3 * 5.  So let's make a 
list of the divisors:

1       1 * 3         1 * 5         1 * 3 * 5
2       2 * 3         2 * 5         2 * 3 * 5
2^2   2^2 * 3       2^2 * 5       2^2 * 3 * 5

That's 12 factors.  Let's try another one, 2^3 * 7^2 = 392

1         1 * 7         1 * 7^2
2         2 * 7         2 * 7^2
2^2     2^2 * 7       2^2 * 7^2
2^3     2^3 * 7       2^3 * 7^2

So that's 12 factors again.  Looks like all numbers have 12 
factors.  Just kidding.  

Anyway, I haven't given you the final answer; there is a 
formula that you can use to find out the number of divisors of 
a number, but I thought I'd let you try to figure it out first 
for yourself.  If you don't get it, you can always write back 
to us and we'll help you out again.

-Doctor Ken, The Geometry Forum

Date: 9/25/95 at 20:50:45
From: Kelly Yu
Subject: Re: Re: Divisor Counting

Hello!

So, what's the formula for finding how many divisors a number 
has?  And how could I find the answer to this question:
"What's the smallest number that has 20 divisors?"

And how can you tell if a number is prime or composite?

Date: 9/27/95 at 20:44:30
From: Doctor Andrew
Subject: Re: Re: Divisor Counting

>So, what's the formula for finding how many divisors a number 
>has? 

Dr. Ken showed you that any number is divisible by the product 
of any of its prime factors.  Remember that you can't use a 
prime factor more than the number of times it appears in the 
factorization of the number.  (i.e. 4 = 2 * 2.  But 8 = 2 * 2 * 
2 is not a divisor of 4).  So if a number n look like this:

n = a^p * b^q * c^r * d^s * e^t * f^u ... ,

where a,b, c and so on are its prime factors, how many 
different how many products can you make out of a,b,c,...?

Well, building a divisor is kind of like making stew.  You grab 
ingredients from the shelf and put them in the pot, but you 
have to decide how much of each ingredient you want, and there 
is a limit on how much you can use. You can use anywhere from 0 
to p a's, 0 to q b's, 0 to r c's and so on.  How many different 
ways can you build a divisor in this way?

Here's an example.  Take the number 12 = 2^2 * 3.

I can put in a 3 or not.  So this will double the number of 
factors I can create from 12/3 = 4 = 2^2.

I can put in 0,1 or 2 2's.  That's three choices.  But I double 
this because I can put in 0 or 1 3.  So I have 6 choices.  Try 
to generalize this to any number.

>And how could I find the answer to this question:
>"What's the smallest number that has 20 divisors?"

Once you've got the formula figured out.  Try some different 
possibilities.  I noticed you suggest 2^19.  It does have 20 
divisors, 

   2^0, 2^1, ... 2^19.

But each time you add a 2 to the factors of your number you 
only get ONE MORE divisor.  Not a very good deal if you ask me.  
Suppose you have the number 4.  So you have 3 divisors, 1, 2 
and 4.  Suppose you toss in another 2 to get 8.  You still only 
have 4 divisors.  But suppose you add a 3 instead.  How many 
divisors do you have now?  I'll be you've got a lot more, and 
only a slightly larger number (12 instead of 8).

>And how can you tell if a number is prime or composite?

If a number n cannot be divided by any numbers less than it 
except for 1, then it is prime.  In fact, you only need to test 
the numbers up to the square root of that number. Look:

Let n be a number and let a^2 = n (a is the square root of n).

Suppose you were testing some number b that is bigger than a to 
see if it divides n and you had already tested all the numbers 
less than b.  So there is some number c such that b * c = n, 
right?  This is part of the definition of being a divisor.

Suppose that c is also bigger than a.  Then b * c must be 
bigger than n, since both b and c are bigger than a (the square 
root of n).  So c must be smaller than a.  But we've already 
checked all the numbers less than b, and a is less than b, so 
we've already checked c.  So when we checked c we should have 
found that it divided n and we could have stopped and declared 
that the number was not prime.

This tells us that if we want to see if a number is prime, we 
only need to test numbers less than or equal to the square root 
of that number.  You can also check only the numbers greater 
than or equal to the square root of the number instead.

If a number is not prime it is composite.  So if you find some 
number that is not 1 or n that divides n, n is composite.

Good luck!

-Doctor Andrew, The Geometry Forum