Understanding proof of $\tau \ (n) =(k_1+1)(k_2+1)\dots(k_r+1)$ and for $\sigma\ (n)$ also.

Question

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:

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.

Note, you've got the formula for $\tau(n)$ wrong, in both the title and body of your question. — Thomas Andrews, Apr 24 '16 at 15:42
Seems to be taken from Elementary Number Theory by David M. Burton. — lhf, Apr 24 '16 at 15:42
@Thomas Andrews In book this is provided. Can u write in comment about it plz. — mnulb, Apr 24 '16 at 15:46
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)$. — Thomas Andrews, Apr 24 '16 at 15:48
It's not clear what part of the above proof confuses you, at least for the case of $\tau$. The case for $\sigma$ is admittedly a little less clear. — Thomas Andrews, Apr 25 '16 at 14:38

score 1 · Accepted Answer · answered Apr 25 '16 at 14:52

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.

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. — mnulb, Apr 26 '16 at 03:33

Understanding proof of $\tau \ (n) =(k_1+1)(k_2+1)\dots(k_r+1)$ and for $\sigma\ (n)$ also.

1 Answers1

Linked