Associated Topics || Dr. Math Home || Search Dr. Math

### 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

```
Associated Topics:
High School Number Theory

Search the Dr. Math Library:

 Find items containing (put spaces between keywords):   Click only once for faster results: [ Choose "whole words" when searching for a word like age.] all keywords, in any order at least one, that exact phrase parts of words whole words

Submit your own question to Dr. Math
Math Forum Home || Math Library || Quick Reference || Math Forum Search