2
$\begingroup$

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}$$

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – kingW3 Jul 7 '18 at 9:51
  • $\begingroup$ There is no "from...to". What you said in words is this formula. $\endgroup$ – Ivan Neretin Jul 7 '18 at 9:51
  • $\begingroup$ 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} $$ $\endgroup$ – robjohn Jul 7 '18 at 13:47
2
$\begingroup$

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}). \,$

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ yep this step is exactly what was missing in my thinking process! $\endgroup$ – ensbana Jul 10 '18 at 21:01
2
$\begingroup$

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...

| cite | improve this answer | |
$\endgroup$
1
$\begingroup$

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.

| cite | improve this answer | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.