# Formula for sum of divisors

I'm reading the proof for the formula for sum of divisors (http://planetmath.org/formulaforsumofdivisors), and get stuck in this one step. I understand that, if $n$ is a positive integer whose factorization into prime factors is $$n = \prod_{i=1}^k p_i^{m_i}$$ then we can express a divisor $d$ of $n$ as $$d = \prod_{i=1}^k p_i^{\mu_i}, where \ 0 \leq \mu_i \leq m_i$$ But how can we then go from "the sum over all divisors becomes the sum over all possible choices for the $\mu_i$'s" to this formula? $$\sum_{d|n} d = \sum_{0 \leq \mu_i \leq m_i} \prod p_i^{\mu_i}$$

• Well for all choices of $0\leq\mu_i\leq m_i$ you get a valid divisor, also for each distinct combination of $\mu_i$'s you get an unique divisor. – kingW3 Jul 7 '18 at 9:51
• There is no "from...to". What you said in words is this formula. – Ivan Neretin Jul 7 '18 at 9:51
• The sum $$\sum_{0\le\mu_i\le m_i} \prod_{i=1}^k p_i^{\mu_i}$$ does not make sense. The $i$ is bound to the product; its scope does not reach the summation. Are you sure that the formula is not $$\prod_{i=1}^k \sum_{0\le\mu_i\le m_i} p_i^{\mu_i}$$ – robjohn Jul 7 '18 at 13:47

The equation $\, d \!=\! \prod_{i=1}^k p_i^{\mu_i}, \,$ where $\, 0 \!\leq\! \mu_i \!\leq\! m_i \,$ gives us a bijection between divisors $\,d\,$ of $\,n\,$ and tuples $\, \mu_i \,$ that satisfy $\, 0 \!\leq\! \mu_i \!\leq\! m_i. \,$ Thus $\, \sum_{d|n} f(d) \,$ uniquely corresponds to $\, \sum_{0 \!\leq\! \mu_i \!\leq\! m_i} f(\prod p_i^{\mu_i}). \,$

• yep this step is exactly what was missing in my thinking process! – ensbana Jul 10 '18 at 21:01

This is just substitution, since for each $d\mid n$, $d=\prod p_i^{\mu_i}$ for some $0\le\mu_i\le m_i$, and vice versa...

Suppose that your number is $72=2^33^2$. Then the divisors are$$1,2,2^2,2^3,3,2\times 3,2^23,2^33,3^2,2\times3^2,2^23^2\text{ and }2^33^2.$$The sum of all these numbers is then$$1+2+2^2+2^3+3+2\times 3+2^23+2^33+3^2+2\times3^2+2^23^2+2^33^2.$$The general case is the same ting.