Toolkit 34

Sum of Positive Divisors

n=p_1^{\alpha_1}p_2^{\alpha_2}\cdots p_k^{\alpha_k}

(1+p_1+p_1^2+\cdots+p_1^{\alpha_1})(1+p_2+p_2^2+\cdots+p_2^{\alpha_2})\cdots(1+p_k+p_k^2+\cdots+p_k^{\alpha_k})

=\frac{p_1^{\alpha_1+1}-1}{p_1-1}\times\frac{p_2^{\alpha_2+1}-1}{p_2-1}\times\cdots\times\frac{p_k^{\alpha_k+1}-1}{p_k-1}

Proof

Suppose

n = p_1^{\alpha_1}p_2^{\alpha_2}\cdots p_k^{\alpha_k}.

Every positive divisor of $n$ has the form

p_1^{\beta_1}p_2^{\beta_2}\cdots p_k^{\beta_k},

where $0 \le \beta_i \le \alpha_i$ . Consider the product

(1+p_1+p_1^2+\cdots+p_1^{\alpha_1})(1+p_2+p_2^2+\cdots+p_2^{\alpha_2})\cdots(1+p_k+p_k^2+\cdots+p_k^{\alpha_k}).

When this product is expanded, we choose one power of each prime $p_i$ . Thus, every resulting term has the form

p_1^{\beta_1}p_2^{\beta_2}\cdots p_k^{\beta_k},

so it is a positive divisor of $n$ . Conversely, every positive divisor of $n$ appears exactly once in this expansion. Therefore, the sum of the positive divisors is

(1+p_1+p_1^2+\cdots+p_1^{\alpha_1})\cdots(1+p_k+p_k^2+\cdots+p_k^{\alpha_k}).

Using the finite geometric-series formula from Toolkit 4,

1+p_i+p_i^2+\cdots+p_i^{\alpha_i} = \frac{p_i^{\alpha_i+1}-1}{p_i-1}.

Hence, the sum of all positive divisors of $n$ is

\frac{p_1^{\alpha_1+1}-1}{p_1-1}\cdot\frac{p_2^{\alpha_2+1}-1}{p_2-1}\cdots\frac{p_k^{\alpha_k+1}-1}{p_k-1}. \quad\square