MathGoldMedalist
Sign InRegister

Toolkit 34

Sum of Positive Divisors

n=p1α1p2α2⋯pkαkn=p_1^{\alpha_1}p_2^{\alpha_2}\cdots p_k^{\alpha_k}
(1+p1+p12+⋯+p1α1)(1+p2+p22+⋯+p2α2)⋯(1+pk+pk2+⋯+pkα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})
=p1α1+1−1p1−1×p2α2+1−1p2−1×⋯×pkαk+1−1pk−1=\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=p1α1p2α2⋯pkαk.n = p_1^{\alpha_1}p_2^{\alpha_2}\cdots p_k^{\alpha_k}.

Every positive divisor of nn has the form

p1β1p2β2⋯pkβk,p_1^{\beta_1}p_2^{\beta_2}\cdots p_k^{\beta_k},

where 0≤βi≤αi0 \le \beta_i \le \alpha_i. Consider the product

(1+p1+p12+⋯+p1α1)(1+p2+p22+⋯+p2α2)⋯(1+pk+pk2+⋯+pkα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}).

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

p1β1p2β2⋯pkβk,p_1^{\beta_1}p_2^{\beta_2}\cdots p_k^{\beta_k},

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

(1+p1+p12+⋯+p1α1)⋯(1+pk+pk2+⋯+pkαk).(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 — Geometric series,

1+pi+pi2+⋯+piαi=piαi+1−1pi−1.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 nn is

p1α1+1−1p1−1⋅p2α2+1−1p2−1⋯pkαk+1−1pk−1.□\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
Back to Toolkit