mathschallenge.net

Frequently Asked Questions

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.