Add Me!Close Menu Navigation

Sum of Divisors

Suppose we define the function \sigma: \mathbb{N} \to \mathbb{N} as the sum of the divisors of n

     $$ \sigma(n) = \sum_{d|n} d $$

Express \sigma(n) in terms of n‘s prime factorization

Let’s just look at a quick example to help us out.

Suppose that we wanted to find the sum of the divisors of 2^3 3^4 5^3. We enumerate these in the following order: first, we decrease the exponent on the 5, then that of 4, and finally 3, like we’re counting in base \mbox{5--3--2}.

    \[2^3 3^4 5^3 + 2^3 3^4 5^2 + 2^3 3^4 5^1 + 2^3 3^4 5^0 + \cdots = 2^3 3^4 (5^0 + 5^1 + 5^2 + 5^3) \cdots\]

Okay, but what about the next 4 terms?

    \begin{align*} 2^3 3^4 (5^0 + 5^1 + 5^2 + 5^3) \cdots &= 2^3 3^4 (5^0 + 5^1 + 5^2 + 5^3) + 2^3 3^3 5^3 + 2^3 3^3 5^2 + 2^3 3^3 5^1 + 2^3 3^3 5^0 + \cdots \\ &= 2^3 3^4 (5^0 + 5^1 + 5^2 + 5^3) + 2^3 3^3 (5^0 + 5^1 + 5^2 + 5^3) + \cdots \\ &= 2^3 (3^3 + 3^4) (5^0 + 5^1 + 5^2 + 5^3) + \cdots \end{align*}

Now, without any loss of generality, the next 12 terms will all be the same, and we’ll end up with 2^3 (3^0 + 3^1 + 3^2 + 3^3 + 3^4) (5^0 + 5^1 + 5^2 + 5^3), at which point we just decrease the exponent on the two, and the same exact operations, again without loss of generality, will eventually lead to

    \[(2^0 + 2^1 + 2^2 + 2^3) (3^0 + 3^1 + 3^2 + 3^3 + 3^4) (5^0 + 5^1 + 5^2 + 5^3)\]

Using the same argument, we can justify that for some arbitrary n factorized as n = \prod_{p} p^{e_p}, then its sum will just be

    \[(p_1^0 + p_1^1 + \cdots + p_1^{e_{p_1}}) \times (p_2^0 + p_2^1 + \cdots + p_2^{e_{p_2}}) \cdots\]

A lot of you may recognize that every one of the clauses are all geometric series, hence we can simplify this expression as

    \[\sigma(n) = \prod_{p_k \mbox{\tiny{ prime}}} \frac{p_k^{e_{p_k}+1}-1}{p_k-1}\ \blacksquare\]

Posted By Lee

Woosh

Recent Comments