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\).
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:
If there is only one distinct prime divisor \(n = p_1^{e_1}\), then there are obviously \(e_1 + 1\) divisors (\(1, p_1, p_1^2, \dots, p_1^{e_1}\)).
If there are two distinct prime divisors \(n = p_1^{e_1} \cdot p_2^{e_2}\), then you can arrange all divisors in form of a tabular.
So the number of divisors is trivially \((e_1 + 1) \cdot (e_2 + 1)\).
We can use the same argument of the previous section.
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.