Number of divisors / sum of divisors

In this article we discuss how to compute the number of divisors \(d(n)\) and the sum of divisors \(\sigma(n)\) of a given number \(n\).

Number of divisors

It should be obvious that the prime factorization of a divisor \(d\) has to be a subset of the prime factorization of \(n\), e.g. \(6 = 2 \cdot 3\) is a divisor of \(60 = 2^2 \cdot 3 \cdot 5\). So we only need to find all different subsets of the prime factorization of \(n\).

Usually the number of subsets is \(2^x\) for a set with \(x\) elements. However this is no longer true, if there are repeated elements in the set. In our case some prime factors may appear multiple times in the prime factorization of \(n\).

If a prime factor \(p\) appears \(e\) times in the prime factorization of \(n\), then we can use the factor \(p\) up to \(e\) times in the subset. Which means we have \(e+1\) choices.

Therefore if the prime factorization of \(n\) is \(p_1^{e_1} \cdot p_2^{e_2} \cdots p_k^{e_k}\), where \(p_i\) are distinct prime numbers, then the number of divisors is:

\[ d(n) = (e_1 + 1) \cdot (e_2 + 1) \cdots (e_k + 1) \]

A way of thinking about it is the following:

\[ \begin{array}{c|ccccc} & 1 & p_2 & p_2^2 & \dots & p_2^{e_2} \\ \hline 1 & 1 & p_2 & p_2^2 & \dots & p_2^{e_2} \\ p_1 & p_1 & p_1 \cdot p_2 & p_1 \cdot p_2^2 & \dots & p_1 \cdot p_2^{e_2} \\ p_1^2 & p_1^2 & p_1^2 \cdot p_2 & p_1^2 \cdot p_2^2 & \dots & p_1^2 \cdot p_2^{e_2} \\ \vdots & \vdots & \vdots & \vdots & \ddots & \vdots \\ p_1^{e_1} & p_1^{e_1} & p_1^{e_1} \cdot p_2 & p_1^{e_1} \cdot p_2^2 & \dots & p_1^{e_1} \cdot p_2^{e_2} \\ \end{array} \]

So the number of divisors is trivially \((e_1 + 1) \cdot (e_2 + 1)\).

Sum of divisors

We can use the same argument of the previous section.

\[ 1 + p_1 + p_1^2 + \dots + p_1^{e_1} = \frac{p_1^{e_1 + 1} - 1}{p_1 - 1} \] \[ \left(1 + p_1 + p_1^2 + \dots + p_1^{e_1}\right) \cdot \left(1 + p_2 + p_2^2 + \dots + p_2^{e_2}\right) \] \[ = \frac{p_1^{e_1 + 1} - 1}{p_1 - 1} \cdot \frac{p_2^{e_2 + 1} - 1}{p_2 - 1} \] \[ \sigma(n) = \frac{p_1^{e_1 + 1} - 1}{p_1 - 1} \cdot \frac{p_2^{e_2 + 1} - 1}{p_2 - 1} \cdots \frac{p_k^{e_k + 1} - 1}{p_k - 1} \]

Multiplicative functions

A multiplicative function is a function \(f(x)\) which satisfies

\[ f(a \cdot b) = f(a) \cdot f(b) \]

if \(a\) and \(b\) are coprime.

Both \(d(n)\) and \(\sigma(n)\) are multiplicative functions.

Multiplicative functions have a huge variety of interesting properties, which can be very useful in number theory problems. For instance the Dirichlet convolution of two multiplicative functions is also multiplicative.

Practice Problems