formula for sum of divisors

If one knows the factorization of a number, one can compute the sum of the positive divisors of that number without having to write down all the divisors of that number. To do this, one can use a formula which is obtained by summing a geometric series.

Theorem 1.

Suppose that $n$ is a positive integer whose factorization into prime factors is ${\mathrm{\prod }}_{i\mathrm{=}\mathrm{1}}^k{p}_i^{m_i}$, where the $p_i$’s are distinct primes and the multiplicities $m_i$ are all at least $\mathrm{1}$. Then the sum of the divisors of $n$ equals

$$\prod _{i=1}^k\frac{p_i^{m_i+1}-1}{p_i-1}$$

and the sum of the proper divisors of $n$ equals

$$\prod _{i=1}^k\frac{p_i^{m_i+1}-1}{p_i-1}-\prod _{i=1}^k{p}_i^{m_i}.$$

Proof.

A number will divide $n$ if and only if prime factors are also prime factors of $n$ and their multiplicity is less than to or equal to their multiplicities in $n$. In other words, a divisors $n$ can be expressed as ${\prod }_{i=1}^k{p}_i^{{\mu }_i}$ where $0\le {\mu }_i\le m_i$. Then the sum over all divisors becomes the sum over all possible choices for the ${\mu }_i$’s:

$$\sum _{d\mid n}d=\sum _{0\le {\mu }_i\le m_i}\prod _{i=1}^k{p}_i^{{\mu }_i}$$

This sum may be expressed as a multiple sum like so:

$$\sum _{{\mu }_1=0}^{m_1}\sum _{{\mu }_2=0}^{m_2}\mathrm{\cdots }\sum _{{\mu }_k=0}^{m_k}\prod _{i=1}^k{p}_i^{{\mu }_i}$$

This sum of products may be factored into a product of sums:

$$\prod _{i=1}^k\left(\sum _{{\mu }_i=0}^{m_i}{p}_i^{{\mu }_i}\right)$$

Each of these sums is a geometric series; hence we may use the formula for sum of a geometric series to conclude

$$\sum _{d\mid n}d=\prod _{i=1}^k\frac{p_i^{m_i+1}-1}{p_i-1}.$$

If we want only proper divisors, we should not include $n$ in the sum, so we obtain the formula for proper divisors by subtracting $n$ from our formula.
∎

As an illustration, let us compute the sum of the divisors of $1800$. The factorization of our number is $2^3\cdot 3^2\cdot 5^2$. Therefore, the sum of its divisors equals

$$\left(\frac{2^4-1}{2-1}\right)\left(\frac{3^3-1}{3-1}\right)\left(\frac{5^3-1}{5-1}\right)=\frac{15\cdot 26\cdot 124}{2\cdot 4}=6045.$$

The sum of the proper divisors equals $6045-1800=4245$,  so we see that $1800$ is an abundant number.

Title	formula for sum of divisors
Canonical name	FormulaForSumOfDivisors
Date of creation	2013-03-22 16:47:35
Last modified on	2013-03-22 16:47:35
Owner	rspuzio (6075)
Last modified by	rspuzio (6075)
Numerical id	14
Author	rspuzio (6075)
Entry type	Theorem
Classification	msc 11A05