I'm currently reading and introductory text for a first semester class that covers a broad range of topics. One of the chapters introduces the $\sigma$ function as the sum of all divisors of a number n.

The text asks the reader to consider the decomposition of an integer n as product of primes

$$n={p}^{\alpha_1}_1 \times {p}^{\alpha_2}_2 \times \dots \times {p}^{\alpha_t}_t \,\,\,\,\,\,\,\,\,\,\,(p_i \text { prime, } \alpha_i \ge 0, \text{ for } i=1,2,\dots,t)$$

And then defines $\sigma(n)$ in the following way:

$$\sigma(n) = \sum_{0 \le e_i \le \alpha_i} {p}^{e_1}_1 \times {p}^{e_2}_2 \times \dots \times {p}^{e_t}_t = (1 + p_1 + {p}^{2}_1 + \dots + {p}^{\alpha_1}_1) \times \dots \times (1 + p_t + {p}^{2}_t + \dots + {p}^{\alpha_t}_t)$$

I'm a newbie and am having difficulty understanding these equalities. Can you help?


First, look at the LHS

$$\sigma(n) = \sum_{0 \le e_i \le \alpha_i} {p}^{e_1}_1 \times {p}^{e_2}_2 \times \dots \times {p}^{e_t}_t$$

There are t independent variables in the sigma, which are $e_1, e_2, ... , e_t$. These run from 0 to the highest power of the associated prime $p_i$ which is found in the prime factorization.

So for each of these values of $e_i$ we have one term. For example if I take the term $p_1 p_2 p_3 ... p_t$ then this is the term which corresponds to $e_i = 1$ for all i. If I take the term $p_1$ then $e_1$ is 1 and all other $e_i$ are 0. This is the expression ${p}^{e_1}_1 \times {p}^{e_2}_2 \times \dots \times {p}^{e_t}_t$ in the summation.

Now look at the RHS

$$(1 + p_1 + {p}^{2}_1 + \dots + {p}^{\alpha_1}_1) \times \dots \times (1 + p_t + {p}^{2}_t + \dots + {p}^{\alpha_t}_t)$$

When we do $(1 + p) (1 + q)$ it expands into $ 1 + p + q + pq $, similarly you can see that $$ (1 + p + p^2)(1 + q) = 1 + p + q + p^2 + pq + p^2q$$

We're basically taking $p_i^0,\ p_i^1, ... p^{e_i}$ and it multiplies with other $p_i$ to combine and generate terms of the form ${p}^{e_1}_1 \times {p}^{e_2}_2 \times \dots \times {p}^{e_t}_t$. And these are generated for all possible combinations of $e_i$, same as what we saw in the sigma symbol.

  • $\begingroup$ Thanks, I believe I understand the transformation now. The RHS is now clear, but I was interpreting the summation in the wrong way. If I understand correctly each exponent in the expression varies independently, right? For instance, for $\sigma(12)$, I'd have $2^0 \times 3^0 + 2^1 \times 3^0 + 2^0 \times 3^1 + 2^1 \times 3^1 + 2^2 \times 3^0 + 2^2 \times 3^1$. $\endgroup$ – bonebroth Nov 23 '17 at 0:16
  • $\begingroup$ @JorgeMarques yes, that is correct. You can actually replace the $\sum$ symbol by t $\sum$ symbols, one for each of the independently varying $e_i$ $\endgroup$ – Peeyush Kushwaha Nov 23 '17 at 5:42

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.