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

### 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/
```
Associated Topics:
High School Permutations and Combinations
Middle School Division

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