formula for sum of divisors


If one knows the factorization of a number, one can compute the sum of the positive divisorsMathworldPlanetmathPlanetmath 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 seriesMathworldPlanetmath.

Theorem 1.

Suppose that n is a positive integer whose factorization into prime factorsMathworldPlanetmath is i=1kpimi, where the pi’s are distinct primes and the multiplicities mi are all at least 1. Then the sum of the divisors of n equals

i=1kpimi+1-1pi-1

and the sum of the proper divisors of n equals

i=1kpimi+1-1pi-1-i=1kpimi.
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 i=1kpiμi where 0μimi. Then the sum over all divisors becomes the sum over all possible choices for the μi’s:

dnd=0μimii=1kpiμi

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

μ1=0m1μ2=0m2μk=0mki=1kpiμi

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

i=1k(μi=0mipiμi)

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

dnd=i=1kpimi+1-1pi-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 233252. Therefore, the sum of its divisors equals

(24-12-1)(33-13-1)(53-15-1)=152612424=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