The Number of Divisors of an IntegerDate: 04/02/98 at 15:40:24 From: Simon Lloyd Subject: Finding the total number of divisors, d(N), of any integer, N Twenty-four has 8 divisors, namely 1,2,3,4,6,8,12 and 24. I have to find a relationship between the integer, N, and the total number of its divisors, d(N). I have found that every prime number will have 2 divisors, every integer which is the square of a prime will have 3 divisors, every integer which is a cube of a prime number will have 4 divisors, etc. Building on this, I've also found that every number can be expressed uniquely as the product of primes and that there is a relationship between the exponents of the primes and d(N). For example, 24 = 2^(3)*3^(1) therefore, d(24) = (3 + 1)(1 + 1) = 8. However, I need to be able to prove this mathematically and explain why it is so, and this is where I'm having problems. I really hope you can help! Date: 04/03/98 at 06:51:14 From: Doctor Anthony Subject: Re: Finding the total number of divisors, d(N), of any integer, N The reasoning you give is correct. You just need to show how it works in general. If a number is a perfect square, it will have an odd number of factors (e.g., 4 has factors 1, 2, 4), whereas all other numbers have an even number of factors. To show that square numbers always have an odd number of factors, consider a square, such as 36. This can be put into prime factors as 2^2*3^2. Note that all its prime factors will be raised to EVEN powers since it is a perfect square. Now, the factor 2 can be chosen in 3 ways, i.e., not at all, once, or twice. And the factor 3 can also be chosen in 3 ways, i.e., not at all, once, or twice. (If neither is chosen, we get the factor 2^0*3^0 = 1.) All together, there will be 3*3 = 9 factors of 36. These are: 1, 2, 3, 4, 6, 9, 12, 18, 36 Now, the important point was made earlier that the prime factors of a perfect square are always raised to some even power, so we could have a^2*b^4*c^2, where a, b, c are primes. In this example: a could be chosen in 3 ways: 0, 1, 2 times b could be chosen in 5 ways: 0, 1, 2, 3, 4 times c could be chosen in 3 ways: 0, 1, 2 times So, all together, the complete number will have 3*5*3 = 45 factors; and note that we are always multiplying odd numbers to get an odd number, 45 in this case. For any number that is not a perfect square, there will ALWAYS be an even number of factors: a^3*b^2*c will have 4*3*2 factors = 24 factors If it is not a perfect square, at least one of its prime factors will be raised to an ODD power, and that means the factor can be chosen in an EVEN number of ways, ensuring that overall there will be an even number of factors. The general rule for the number of factors is to increase the powers of the factors by 1 and multiply these together. So: a^n*b^m*c^p will have (n + 1)(m + 1)(p + 1) factors. 2^3*5^4*7^2 will have 4*5*3 = 60 factors -Doctor Anthony, 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-2015 The Math Forum
http://mathforum.org/dr.math/