sum of the factors of any natural number

Question

prove that the sum of all the factors of any natural number is=(a^p+1 -1)/a-1*......

---

[YF] Here is one possible interpretation of the above:

Prove the formula for the sum-of-divisors function $$\sigma\left(\prod_i p_i^{a_i}\right) = \prod_i \frac{p_i^{a_i+1}-1}{p_i-1}.$$

Answer 1

I assume you are referring to the identity of the divisor function $$\sigma (n) = \displaystyle\prod_{i=1}^r\frac{p_i^{\alpha_i+1}-1}{p_i-1}$$ where $n = p_1^{\alpha_1} p_2^{\alpha_2} \dots p_r^{\alpha_r}$.

This is derived by showing that $\sigma$ is multiplicative and that the sum of the divisors of a prime power $p^k$ is the sum $1 + p + p^2 + \dots + p^k = \frac{p^{k+1}-1}{p-1}$.

To show $\sigma$ is multiplicative, let $a, b \in \mathbb{N}$, with $\gcd(a,b)=1$. Since any prime that divides $ab$ must divide either $a$ or $b$, as they share no common factors, the sum of divisors of $ab$ must be exactly the sum of the divisors of $a$ multiplied with the sum of the divisors of $b$, as the product of any divisor of $a$ and any divisor of $b$ must also be a unique divisor of $ab$ (see Arturo's answer for a more complete proof). Thus $\sigma(ab) = \sigma(a)\sigma(b)$. Since any two primes are coprime, you can decompose $\sigma(n)$ into $\displaystyle\prod_{i=1}^r \sigma(p_i^{\alpha_i})$, and use the hint I mentioned earlier.

Answer 2

The proof is in any standard book in number theory; it breaks into four steps, two of which are number theoretic, the other is basic algebra.

1. If $p$ is a prime, and $n$ is a positive integer, then $\sigma(p^n) = 1+p+p^2+\cdots+p^n$.

   Indeed, the only divisors of $p^n$ are the powers of $p$ with exponent less than or equal to $n$, that is, $p^0 = 1$, $p$, $p^2,\ldots,p^n$. So $\sigma(p^n)$ is their sum.

2. If $x$ is any number different from $1$, and $n$ is a positive integer, then $1+x+\cdots+x^n = \frac{x^{n+1}-1}{x-1}$.

   Simply notice that $(1+x+\cdots+x^n)(x-1) = x+\cdots +x^{n+1}-(1+\cdots+x^n) = x^{n+1}-1$. Since $x\neq 1$, then $x-1\neq 0$, so divide both sides by $x-1$ to get the identity.

   In particular, $\sigma(p^n) = 1+p+\cdots+p^n = \frac{p^{n+1}-1}{p-1}$.

3. If $r$ and $s$ are relatively prime, then $\sigma(rs)=\sigma(r)\sigma(s)$.

   Suppose $k$ divides $rs$. Let $b=\gcd(k,r)$, $c=\gcd(k,s)$. Because $r$ and $s$ are relatively prime, $bc=k$. That is: every divisor of $rs$ is the product of a divisor of $r$ and a divisor of $s$. Conversely, if $b|r$ and $c|s$, then $bc|rs$, so the product of a divisor of $r$ and a divisor of $s$ is a divisor of $rs$.

   That is, every summand in $\sigma(rs)$ is the product of a particular summand in $\sigma(r)$, and a particular summand of $\sigma(s)$. That is, $\sigma(rs)=\sigma(r)\sigma(s)$.

4. Induction: if $n=p_1^{a_1}\cdots p_r^{a_r}$, then $\sigma(n)=\prod\sigma(p_i^{a_i})$.

   The result holds if $r=1$ trivialy, and if $r=2$ by the previous step. Assume the result holds for $k$ distinct prime factors, and $n=p_1^{a_1}\cdots p_r^{a_r}p_{r+1}^{a_{r+1}}$. Let $n_1=p_1^{a_1}\cdots p_r^{a_r}$, $n_2=p_{r+1}^{a_{r+1}}$. Then $n=n_1n_2$, and $\gcd(n_1,n_2)=1$, so $\sigma(n)=\sigma(n_1)\sigma(n_2)$. Now apply induction to $\sigma(n_1)$, and the formula to $\sigma(n_2)$.

And that's it.