## You are here

Homeformula for sum of divisors

## Primary tabs

# 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 $\prod_{{i=1}}^{k}p_{i}^{{m_{i}}}$, where the $p_{i}$’s are distinct primes and the multiplicities $m_{i}$ are all at least $1$. Then the sum of the divisors of $n$ equals

$\prod_{{i=1}}^{k}{p_{i}^{{m_{i}+1}}-1\over p_{i}-1}$ |

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

$\prod_{{i=1}}^{k}{p_{i}^{{m_{i}+1}}-1\over 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\leq\mu_{i}\leq 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\leq\mu_{i}\leq 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}}}\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}{p_{i}^{{m_{i}+1}}-1\over 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({2^{4}-1}\over{2-1}\right)\left({3^{3}-1}\over{3-1}\right)\left({5^{3}-1% }\over{5-1}\right)={15\cdot 26\cdot 124\over 2\cdot 4}=6045.$ |

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

## Mathematics Subject Classification

11A05*no label found*

- Forums
- Planetary Bugs
- HS/Secondary
- University/Tertiary
- Graduate/Advanced
- Industry/Practice
- Research Topics
- LaTeX help
- Math Comptetitions
- Math History
- Math Humor
- PlanetMath Comments
- PlanetMath System Updates and News
- PlanetMath help
- PlanetMath.ORG
- Strategic Communications Development
- The Math Pub
- Testing messages (ignore)

- Other useful stuff
- Corrections