Tuesday, 13 October 2015

HOW MANY DIVISORS DOES A NUMBER HAVE?

--------------------------------------------------------------------------------------------------------------------------
READ MORE:
http://www.javascripter.net/math/calculators/primefactorscalculator.htm
http://mathschallenge.net/problems/pdfs/mathschallenge_1_star.pdf
https://en.wikipedia.org/wiki/Euler%27s_totient_function#Divisor_sum
https://en.wikipedia.org/wiki/Prime_number_theorem#Proof_sketch
https://www.youtube.com/watch?v=5VW1gEnZGdY
http://www.wikihow.com/Determine-the-Number-of-Divisors-of-an-Integer
http://mathcentral.uregina.ca/QQ/database/QQ.02.06/joe1.html

http://mathforum.org/library/drmath/view/55843.html

http://primes.utm.edu/glossary/xpage/tau.html

--------------------------------------------------------------------------------------------------------------------------

How many divisors does a number have?

Suppose you wish to find the number of divisors of 48. Starting with 1 we can work through the set of natural numbers and test divisibility in each case, noting that divisors can be listed in factor pairs.

48 = 1×48 = 2×24 = 3×16 = 4×12 = 6×8

Hence we can see that 48 has exactly ten divisors. It should also be clear that, using this method, we only ever need to work from 1 up to the square root of the number.

Although this method is quick and easy with small numbers, it is tedious and impractical for larger numbers. Fortunately there is a quick and accurate method using the divisor, or Tau, function.

Let d(n) be the number of divisors for the natural number, n.

We begin by writing the number as a product of prime factors: n = p^aq^br^c...
then the number of divisors, d(n) = (a+1)(b+1)(c+1)...

To prove this, we first consider numbers of the form, n = p^a. The divisors are 1, p, p², ..., p^a; that is, d(p^a)=a+1.

Now consider n = p^aq^b. The divisors would be:

1	`p`	`p`²	...	`p`^a
`q`	`pq`	`p`²`q`	...	`p`^a`q`
`q`²	`pq`²	`p`²`q`²	...	`p`^a`q`²
...	...	...	...	...
`q`^b	`pq`^b	`p`²`q`^b	...	`p`^a`q`^b

Hence we prove that the function, d(n), is multiplicative, and in this particular case, d(p^aq^b)=(a+1)(b+1). It should be clear how this can be extended for any natural number which is written as a product of prime factors.

The number of divisor function can be quickly demonstrated with the example we considered earlier: 48 = 2⁴×3¹, therefore d(48)=5×2=10.

How to Determine the Number of Divisors of an Integer

One Methods:Why This Works

1, 2, 3, 4, 6, 8, 12, 24 are all divisors (or factors) of 24. You can divide 24 by any of them and you will arrive at a whole number. So there are 8 divisors of the number 24. This article tells you how to calculate this number quickly.

Steps

1

As an example, we calculate the number of divisors of 24. First we factor the number. 24 = 2³*3
2

Note the exponents. These are 3 and 1. When a number doesn’t have an exponent its exponent equals 1.
3

Add one to each of the exponents and multiply. (3+1)*(1+1) = 4*2 = 8. The number of divisors is 8.

Why This Works

This is not a rigorous proof, it’s an explanation.

A number d is a divisor of 24 when d is a positive integer, and the result of the division, n, is an integer. This means that any d must be of the form 2^p*3^q, where p and q are integers. Furthermore p<=3, q<=1, otherwise n would still not be an integer. p and q are nonnegative, otherwise d is not an integer.
Remember that any nonzero number raised to the zeroth power equals 1. So p and q can also be 0. So p can be 0, 1, 2, or 3 which gives for 4 possibilities for p. q can be 0 and 1, which gives 2 possibilities for q. The number of possibilities is just one larger than the corresponding exponent.
Because these possibilities are independent we can multiply them in order to arrive at the total number of divisors.

Some examples

17 = 17¹ --> 2
25 = 5² --> 3
60 = 2²*3*5 --> 12
100 = 2²*5² --> 9
45360 = 2⁴*3⁴*5*7 --> 100

How many divisors does the number 138600 have? And is there a specific way to figure this out?

Joe,

There is a nice way to determine the number of divisors of a positive integer and I am going to illustrate it with a smaller number, 360.

The first step is to write the prime factorization of 360

360 = 2³ 3² 5¹

We are looking for divisors of 360 so suppose that n divides 360. Notice that if an integer divides n it also divides 360 so, in particular, if a prime divides n then that prime must be 2, 3 or 5. Hence n can be written

n = 2^r 3^s 5^t

You have to be a little careful here since, for example 36 divides 360 but

36 = 2² 3²

so I use the convention that a⁰ = 1 and write

36 = 2² 3² 5⁰

What are the possible values of r, s and t? r can be 0, 1, 2 or 3. (r can't be 4 since 2⁴does not divide 360.) likewise s can be 0, 1 or 2 and t can be 0 or 1. Hence if you are going to construct a divisor n of 360 you can form

n = 2^r 3^s 5^t

with 4 choices for r (0, 1, 2 or 3), 3 choices for s (0, 1 or 2) and 2 choices for t (0 or 1), hence there are

4 3 2 = 24

ways you can form n and thus 360 has 24 divisors.

Thus to calculate the number of divisors of 360

- write the prime factorization of 360 [360 = 2³ 3² 5¹]
- look at the powers in the prime factorization [3, 2, 1]
- add 1 to each power [(3 + 1), (2 + 1), (1 + 1)]
- find the product of these numbers [4 3 2 = 24]

Check this method with another number like 140. It's prime factorization is

2 x 2 x 5 x 7.

So that should be 3 choice x 2 choices x 2 choices = 12 divisors. Here they are: 1, 2, 4, 5, 7, 10, 14, 20, 28, 35, 70, 140.

Steve and Penny

The Number of Divisors of an Integer

Date: 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/