# Sum of the factors of any natural number

Prove that the sum of all the factors of any natural number is equal to $\frac{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}.$$

-
What is a? p? What natural number? –  Aryabhata Jan 16 '11 at 19:16
You'll have to de better than that, user5918. –  TonyK Jan 16 '11 at 19:24
The math library is your friend. –  Yuval Filmus Jan 16 '11 at 19:29
@Yuval: Please don't substantially edit questions without clarification from OP. It might not have been the question intended by OP. –  Aryabhata Jan 16 '11 at 19:31
If not, then it should have been! Frankly, I'm not sure even the OP themselves knew exactly what the question they were after was. –  Yuval Filmus Jan 16 '11 at 21:07

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.

-

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.

-
COULD YOU EXPLAIN IN LITTLE MORE DETAIL –  user5918 Jan 16 '11 at 20:10
@user5918: No need for the caps lock. I will update. –  Brandon Carter Jan 16 '11 at 20:23