formula for sum of divisors

If one knows the factorization of a number,one can compute the sum of the positive divisors ofthat number without having to write downall the divisors of that number. To dothis, one can use a formula which is obtainedby summing a geometric series.

Theorem 1.

Suppose that $n$ is a positive integer whose factorizationinto prime factors is ${\mathrm{\prod }}_{i\mathrm{=}\mathrm{1}}^k{p}_i^{m_i}$,where the $p_i$’s are distinct primes and themultiplicities $m_i$ are all at least $\mathrm{1}$. Thenthe 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 primefactors are also prime factors of $n$ andtheir multiplicity is less than to or equalto their multiplicities in $n$. In otherwords, a divisors $n$ can be expressedas ${\prod }_{i=1}^k{p}_i^{{\mu }_i}$ where $0\le {\mu }_i\le m_i$. Then the sum over all divisorsbecomes the sum over all possible choicesfor 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 multiplesum 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 intoa 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 ageometric 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 shouldnot include $n$ in the sum, so we obtainthe formula for proper divisors by subtracting$n$ from our formula.
∎

As an illustration, let us compute the sumof the divisors of $1800$. The factorizationof 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.