Number of Divisors of a Number

Hello. This lesson will cover an important application of all possible selections – finding out the number of divisors of a number.

Let’s consider a number N = 72. I wish to find out the number of divisors of this number. If we count manually, the divisors are – 1, 2, 3, 4, 6, 8, 9, 12, 18, 24, 36, 72 – total 12 in number. Things will obviously get ugly when N gets large.

To count the number of divisors, let’s factorize N as 2332.

Now here’s the logic: I have a collection of three 2s and two 3s: [2, 2, 2, 3, 3]. If I select any number of numbers from this collection and multiply them together, I’ll obtain a factor of N. And selecting nothing will mean obtaining 1 as the factor.

For example, from the lot [2, 2, 2, 3, 3], I could select [2, 2, 3] and multiply them I get 12, which is a factor of 72. Or, I could select [3, 3] and multiply to obtain 9 which is again a factor of 72. If I select only [2], then there’s no need to multiply – I’ve simply obtained 2 as a factor.

That means, the number of factors will be same as the number of selections possible from the lot [2, 2, 2, 3, 3].

That is, the total number of selections possible from a lot of three identical objects of one type (the 2s) and two identical objects of the second type (the 3s).

The required answer will be (3 + 1)(2 + 1) = 12 – the same answer as we obtained by manual counting.

Refer to the examples in the previous lesson, in case you’re unsure of the calculations.

What if the number was 324 (i.e. 2234)? Then the lot from which the selections are to be made will be [2, 2, 3, 3, 3, 3]. The answer will be (2 + 1)(4 + 1) = 15. That is, all possible combinations from a lot of two identical things of one type (the 2s) and four identical things of another type (the 3s).

You may list out the factors and count them manually, if you don’t trust me.

And what if the number was 1800. Then our lot would have been [2, 2, 2, 3, 3, 5, 5]. The answer would be (3 + 1)(2 + 1)(2 + 1) = 36 factors.

Let’s generalize now. Suppose we have a number N = 2α3β5γ Then the number of factors of N will be same as the number of combinations from a collection of ‘α’ number of 2s, ‘β’ number of 3s, ‘γ’ number of 5s (and δ number of 7s etc.). The number of factors will be (α + 1)(β + 1)(γ + 1).

Neat!

Lesson Summary

1. The number of factors of the number N = 2α3β5γ… will be (α + 1)(β + 1)(γ + 1)…

See you in the next lesson with some examples.