How many divisors (also called factors) does a number have? We’ve answered many questions about that over the years, sometimes by just guiding a student to discover it, sometimes either deriving the formula for them or just showing and using it. Let’s look at a few.
Discovering the trick
We’ll start with a question from 1995, in which Kelly presented us with an investigation assignment she was given:
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 page. 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.
This is very open-ended; Kelly appears to have approached it not by experimenting for herself as intended, but by searching for ready-made answers. Doctor Ken chose to guide her investigation rather than show the formula:
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 prime 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.
If all the prime factors of a are factors of b, then every divisor of a is a divisor of b. On the other hand, if any prime factors of a are not factors of b, then a can’t be a divisor of b.
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.
Every combination of prime factors of a number gives us a divisor of that number. Can you see the pattern Doctor Ken used to list them?
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.
Building a divisor, making stew
Kelly wrote back without showing any work of her own, just asking for the formula and the answer to one of the questions:
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?"
Doctor Andrew replied this time, again offering ideas to think about rather than an actual formula, but leading very close:
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 looks 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 products can you make out of a, b, c, ...?
That is, given the prime factorization of any number, we want to count the ways to put those primes together to make divisors.
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?
We’ll be choosing how many of each prime to use:
Here's an example. Take the number 12 = 2^2 * 3. 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.
There are 3 numbers with no 3 (1, 2, 4), and 3 more with one 3 (3, 6, 12). Those are all the divisors.
How about the smallest number with 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).
The number \(2^{19} = 524,288\) does have 20 divisors, but there are smaller numbers that work. We’ll be seeing that soon.
Developing a formula
Two years later, Ryan sent us exactly the same assignment:
Divisors 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
Doctor Anthony gave a direct answer, first carrying out a specific example as we’ve already seen, and then stating the formula in general:
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.
This is the same example we saw before. There are 3 ways to choose how many 2’s to use, and for each of those, 2 ways to choose how many 3’s, making a total of \(3\times 2 = 6\) ways.
Can we generalize the method? It’s hard to write as an actual formula because the number of prime factors can vary; but we can express the idea:
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.
So our calculation for \(12 = 2^{\color{Red} 2}\times3^{\color{Blue} 1}\) is \(({\color{Red} 2}+1)({\color{Blue} 1}+1) = 3\times2 = 6\).
How about that last question?
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.
Taking this more slowly, the count of 20 could be obtained as
- \(20 = 20\), requiring the form \(a^{19}\), whose smallest value is \(2^{19} = 524,288\) as we saw before, or
- \(20 = 10\times 2\), requiring the form \(p^{11} \times q^1\), which can be as small as \(2^9 \times 3^1 = 1536\), or
- \(20 = 5\times 4\), requiring the form \(p^4 \times q^3\), which can be as small as \(2^4 \times 3^3 = 432\), or
- \(20 = 5\times 2\times 2\), requiring the form \(p^4 \times q^1\times r^1\), which can be as small as \(2^4\times 3^1\times 5^1 = 240\).
The last is the smallest.
Here is a similar problem, looking for the smallest number with 30 factors:
Factoring
The number with the most factors
Here’s a question from 1999 that applies the formula in the opposite way to what we just did:
Counting the Number of Factors Is there an easier way other than trial and error to find the number less than 100 that has the greatest number of factors?
Doctor Rob answered, first stating our formula in words, with a brief explanation:
Yes, there is an easier way. If you factor a number into its prime power factors, then the total number of factors is found by adding one to all the exponents and multiplying those results together. Example: 108 = 2^2*3^3, so the total number of factors is (2+1)*(3+1) = 3*4 = 12. Sure enough, the factors of 108 are 1, 2, 3, 4, 6, 9, 12, 18, 27, 36, 54, and 108. This happens because to be a factor, a number must have the same primes, and raised to the same or lower powers. Each factor of 108 must be a power of 2 times a power of 3, and the exponent of 2 can be 0, 1, or 2, and the exponent of 3 can be 0, 1, 2, or 3. There are three choices for the exponent of 2 and 4 choices for the exponent of 3, for a total of 3*4 = 12 possible choices. Each gives a different factor, so there are 12 factors.
Sounds simple now, doesn’t it?
Now we try to make as many factors as possible, for each number of prime factors:
Now to create small numbers with many factors, you should use the smallest primes. The larger the exponents, the more factors you will have, but you have to keep the number less than 100, so the exponents cannot be too large. If there is only one prime, it should be 2. To stay less than 100, the exponent can be at most 6, since 2^7 = 128 > 100. 2^6 = 64 has 6+1 = 7 factors.
So candidate #1 is \(64 = 2^6\), with 7 factors.
If there are two primes, they should be 2 and 3. To stay less than 100, the exponent of 3 can be at most 4, since 3^5 = 243 > 100. Consider numbers of the form a power of 2 times 3, 3^2, 3^3, or 3^4. Pick the power of 2 as large as possible while staying under 100. Compute the number of factors, and keep the champion(s).
This will give us several more candidates, which we’ll list below. They’ll be \(2^5 3^1 = 96\), \(2^4 5^1 = 80\), and \(3^1 5^2 = 75\). These have, respectively, 12, 10, and 6 factors, so 96 is the best so far.
If there are three primes, they should be 2, 3, and 5. To stay less than 100, the exponent of 5 can be at most 2, since 5^3 = 125 > 100. Consider numbers of the form a power of 2 times a power of 3 times 5 or 5^2. Pick a power of 3 which keeps you under 100, then pick the power of 2 as large as possible while staying under 100. Compute the number of factors, and keep the champion(s). There cannot be four or more primes, because 2*3*5*7 = 210 > 100.
We have a number of possibilities, so we need to be organized:
You get the following table, in which you can complete the last column:
Exponent of 2 Exponent of 3 Exponent of 5 N Number of Factors
6 0 0 64 7
5 1 0 96
3 2 0 72
0 4 0 81 5
4 0 1 80
2 1 1 60
1 2 1 90
1 0 2 50 6
0 1 2 75 6
This systematic procedure is better than trial and error.
Here I’ve filled in the table, so we can see the answer:
Exponent of 2 Exponent of 3 Exponent of 5 N Number of Factors
6 0 0 64 7
5 1 0 96 12
3 2 0 72 12
0 4 0 81 5
4 0 1 80 10
2 1 1 60 12
1 2 1 90 12
1 0 2 50 6
0 1 2 75 6
So 60, 72, 90, and 96 all have the most possible divisors, which is 12.
For the same problem, but up to 1,000,000 rather than just 100, see this long discussion:
Multiple Personality Numbers
Finding a number with 5 factors
We’ll close with a 2002 problem from a teacher-to-be:
Factoring Strategies I am returning to school and I am having a very hard time in a math for elementary teachers class. The objective is to teach for understanding. My assignment is to explore strategies that help you find a number having 5 factors and a number having 13 factors and to explain my thinking and strategies. So far I think I have found that the number has to be a square number because square numbers have an odd number of factors. For example, 16 = 1, 2, 4, 8, and 16, but I need to know why. Is there a way I can know a number has 13 factors without wrecking my brain factoring all of the square numbers? Please don't use x = y z and so on; I do not understand what all that means.
A future teacher ought to be able to handle variables; but it’s also important to be able to communicate with students who are not ready for that. I replied:
It's hard to discuss this problem without using variables; that's sort of like telling certain people to talk without moving their hands! But I'll try. That means I'll mostly have to use examples.
Let's look at the factors of a square number, first; say, 6^2 = 36:
1*36
2*18
3*12
4*9
6*6
9*4
12*3
18*2
36*1
Here I listed not just the factors, but the factor pairs. That is, for each factor, there is another number you multiply it by to get 36, and I included it in my list. We have 9 factors, and 9 factor pairs.
Of course, these are ordered pairs (for a reason); there are really 5 different pairs of factors.
Notice that every factor appears twice in the list, once as the first member of a pair, and once as the second. That means that the rows can be paired off - except for the 6*6 row:
1*36 --------+
2*18 ------+ |
3*12 ----+ | |
4*9 --+ | | |
6*6 o | | | |
9*4 --+ | | |
12*3 ----+ | |
18*2 ------+ |
36*1 --------+
The only exception is the 6*6 row, because there both occurrences of 6 are in the same row.
The factor 6 is “paired” with itself!
Now, when you can pair everything up, you have an even number; when you can't you have an odd number. In this case, we have an odd number of rows, namely 9 factors. If the number were not a square, we would have an even number of rows, because there would be no special row like 6*6. For example, here are the factor pairs for 35:
1*35 ---+
5*7 -+ |
7*5 -+ |
35*1 ---+
Here every factor pairs up with another in a different row, and there is an even number of them.
Does that demonstrate why you need a square in order to have an odd number of factors?
We’ll see another argument below.
Counting divisors, elementary version
So far, I haven’t used the divisor-counting formula. I introduced that with an example:
Now things will get a little more complicated, because I'm going to show how you can find the number of factors without listing them. Let's work with 36 again. First we'll find the prime factorization:
36 = 2*2*3*3
Now, when we make a factor pair, what we are really doing is just splitting these prime factors up between two numbers. For example, the factor pair 3*12 is
36 = 3 * 2*2*3
where I took 3 for the first factor, and all the rest for the second. Do you see why this has to be true? When you multiply two numbers together, the prime factors of the product are the prime factors of the factors, combined; we're just pulling them apart.
That tied the idea to the factor pairs we’d been considering; now we can make a list of divisors and relate it to the choice of exponents:
Now, how many ways can you split up the prime factors of a number? Let's make a table, listing how many of each prime factor we use for the first factor:
number number product of
of 2's of 3's 2's and 3's
--------+--------+------------
0 | 0 | 2^0*3^0 = 1
0 | 1 | 2^0*3^1 = 3
0 | 2 | 2^0*3^2 = 9
1 | 0 | 2^1*3^0 = 2
1 | 1 | 2^1*3^1 = 6
1 | 2 | 2^1*3^2 = 18
2 | 0 | 2^2*3^0 = 4
2 | 1 | 2^2*3^1 = 12
2 | 2 | 2^2*3^2 = 36
I can choose anything up to the maximum number of 2's in 36, namely 0, 1, or 2 of them; and the same with the 3's. Altogether, this gives me 3 times 3, or 9, ways to choose the prime factors I want to use; and that gives me 9 factors of 36.
Now we can do the same without explicit reference to exponents, which might be better for younger students:
Just in case you're not fully comfortable with powers (especially when the exponent is 0), here's another way to look at the same thing:
product of
2's 3's 2's and 3's
--------+--------+-------------------
| | 1 = 1
| 3 | 1 * 3 = 3
| 3*3 | 1 * 3*3 = 9
2 | | 1 * 2 = 2
2 | 3 | 1 * 2 * 3 = 6
2 | 3*3 | 1 * 2 * 3*3 = 18
2*2 | | 1 * 2*2 = 4
2*2 | 3 | 1 * 2*2 * 3 = 12
2*2 | 3*3 | 1 * 2*2 * 3*3 = 36
Nothing is different here except for the notation.
I'll leave it to you to generalize this idea, and try it on some other numbers. The idea is that you count the number of each prime factor in your number; the number of factors will be one more than the number of each prime factor, all multiplied together. In this case, we had two 2's and two 3's, so (2+1)*(2+1) = 3*3 gives 9 factors. For 35, we have one 5 and one 7, so the number of factors is (1+1)*(1+1) = 2*2 = 4, as we saw.
Observe that in order to get an odd number of factors, we can’t have any even factors; so each exponent must have been even. That forces the original number to be a square.
Now you need to apply this to your problem. If a number has 13 factors, what does that tell you about its prime factors? Can you find a number like this? Can you find more of them?
Again, it has to be a square; and because 13 is prime, it has to be something like \(2^{12} = 4096\) (or the 12th power of some other prime, which would be much larger).
Pingback: Counting Divisors – with Conditions – The Math Doctors
Pingback: The Locker Problem – The Math Doctors
Pingback: Summing Divisors – The Math Doctors
Pingback: Prime Numbers: What and Why – The Math Doctors