Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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}.$$

share|improve this question
    
What is a? p? What natural number? –  Aryabhata Jan 16 '11 at 19:16
1  
You'll have to de better than that, user5918. –  TonyK Jan 16 '11 at 19:24
1  
The math library is your friend. –  Yuval Filmus Jan 16 '11 at 19:29
1  
@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
2  
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
show 1 more comment

2 Answers

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.

share|improve this answer
add comment

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.

share|improve this answer
    
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
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.