# 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 |