I recently studied that: $$\tau \ (n) = (k_1+1)(k_2+1) \cdots (k_{r}+1)$$ $$\sigma\ (n) = \frac{p_{1}^{k_1 + 1} -1}{p_1 - 1}{\frac{p_{2}^{k_2 + 1} -1}{p_2 - 1}} \cdots {\frac{p_{r}^{k_r + 1} -1}{p_r - 1}}$$ and proof of this goes something like:enter image description here

Theorem 6-1 states that : If $n = p_{1}^{k_{1}}{p_{2}^{k_{2}}} \cdots {p_{r}^{k_{r}}}$ is the prime factorization of $n > 1$, then the positive divisors of $n$ are precisely those integers d of the form $$d = p_{1}^{a_{1}}{p_{2}^{a_{2}}} \cdots {p_{r}^{a_{r}}}$$ where $0 \leq\ a_i\leq\ k_i\ (i = 1,\ 2 \cdots,\ r)$

And finally I want to know how there can be $k+1$ choices for $a_1$ and why $(k_1+1)(k_2+1) \cdots (k_r + 1)$ produces possible divisors of $n$.

And in similar fashion why and how $(1 + p_1 + p_1^2 + \cdots + p_1^{k_1})(1 + p_2 + p_2^2 + \cdots + p_{2}^{k_2}) \cdots (1 + p_r + p_r^2 +\cdots + p_r^{k_r})$ give sum of divisors.

Please write in elementary way.

  • $\begingroup$ Note, you've got the formula for $\tau(n)$ wrong, in both the title and body of your question. $\endgroup$ – Thomas Andrews Apr 24 '16 at 15:42
  • $\begingroup$ Seems to be taken from Elementary Number Theory by David M. Burton. $\endgroup$ – lhf Apr 24 '16 at 15:42
  • $\begingroup$ @lhf yes from D.M Burton $\endgroup$ – mnulb Apr 24 '16 at 15:44
  • $\begingroup$ @Thomas Andrews In book this is provided. Can u write in comment about it plz. $\endgroup$ – mnulb Apr 24 '16 at 15:46
  • $\begingroup$ You've written, three times $(k+1)(k+2)\dots(k_r+1)$, while the book has $(k_1+1)(k_2+1)\dots(k_r+1)$. $\endgroup$ – Thomas Andrews Apr 24 '16 at 15:48

The key to both proofs is that if $n=ab$ with $a$ and $b$ relatively prime, then any divisor $d$ of $n$ can be written uniquely as a product $d=d_ad_b$ where $d_a\mid a$ and $d_b\mid b$.

This in turn means that:

$$\begin{align}\tau(n)&=\sum_{d\mid n} 1\\ & = \sum_{d_a\mid a,d_b\mid b} 1 \\ &= \left(\sum_{d_a\mid a} 1\right)\left(\sum_{d_b\mid b} 1\right) \\ &= \tau(a)\tau(b)\\ \sigma(n)&=\sum_{d\mid n} d \\ &= \sum_{d_a\mid a,d_b\mid b} d_ad_b \\ &= \left(\sum_{d_a\mid a} d_a\right)\left(\sum_{d_b\mid b} d_b\right) \\ &= \sigma(a)\sigma(b) \end{align}$$

This lets us conclude, by induction on $k$, that if $p_1,p_2,\dots,p_k$ are distinct primes then: $$\tau\left(p_1^{a_1}p_2^{a_2}\cdots p_k^{a_k}\right) = \tau\left(p_1^{a_1}\right)\cdots \tau\left(p_k^{a_k}\right)\\ \sigma\left(p_1^{a_1}p_2^{a_2}\cdots p_k^{a_k}\right) = \sigma\left(p_1^{a_1}\right)\cdots \sigma\left(p_k^{a_k}\right)$$

So now all you have to do is convince yourself that $\tau(p_i^{a_i})=a_i+1$ and $\sigma(p_i^{a_i})=1+p_i+p_i^2+\dots + p_i^{a_i}$.

A function $f$ is said to be "multiplicative" if $f(ab)=f(a)f(b)$ when $a,b$ are relatively prime. There is a general rule that if $f$ is multiplicative, then:

$$g(n)=\sum_{d\min n} f(d)$$

is also multiplicative.

In the above two cases, we that $f(n)=1$ for $\tau$ and $f(n)=n$ for $\sigma$.

All multiplicative functions can be computed by computing the values at their prime factorizations.

| cite | improve this answer | |
  • $\begingroup$ I more doubt, we had taken $n=\left(p_1^{a_1}\right)\cdots $. Then divisors of $p_1^{a_1}$ will also divide $n$ and divisors of other will do the same. Then suppose we got $3$ divisors from first and $2$ from second then we should add these why multiplication happen. I'm asking this from logical point of view and understand this becoz of multiplicative functions. $\endgroup$ – mnulb Apr 26 '16 at 3:33

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.