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