DivisorsDate: 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/ |
Search the Dr. Math Library: |
[Privacy Policy] [Terms of Use]
Ask Dr. Math^{TM}
© 1994-2013 The Math Forum
http://mathforum.org/dr.math/