sum of factors

Printable View

June 24th 2009, 08:03 AM
jashansinghal

sum of factors

What is the sum of all factors of 45000 which are divisible by 10
June 24th 2009, 09:38 AM
TheAbstractionist

That would be 10 times the sum of all the factors of 4500. The sum-of-factors function $\sigma$ has the following property: if $n=p_1^{k_1}\cdots p_r^{k_r}$ where the $p_i$ are distinct primes, then

$\sigma(n)\ =\ \prod_{i\,=\,1}^r\frac{p_i^{k_i+1}-1}{p_i-1}$

Thus $\sigma(4500)\,=\,\sigma(2^23^25^3)\,=\,\left(\frac {2^3-1}{2-1}\right)\left(\frac{3^3-1}{3-1}\right)\left(\frac{5^4-1}{5-1}\right)\,=\,7\cdot13\cdot156\,=\,14196.$ So the answer to the problem is 141960.
June 25th 2009, 01:30 AM
jashansinghal

can u give an easy method
June 25th 2009, 06:23 AM
TheAbstractionist

I don’t see anything wrong with the proof, particularly the formula

$\sigma(n)\ =\ \prod_{i\,=\,1}^r\frac{p_i^{k_i+1}-1}{p_i-1}$

Shall we prove this formula? Then perhaps you’ll feel less afraid of using it. (Wink)

First, we prove that if $\gcd(m,n)=1$ then $\sigma(mn)=\sigma(m)\sigma(n).$ Note that a divisor $d$ of $mn$ can be written as $d=ef$ where $e\mid m$ and $f\mid n$ and $\gcd(e,f)=1.$ Hence

$\sigma(mn)\,=\,\sum_{d\,\mid\,mn}d$

$=\,\sum_{e\,\mid\,m\,f\,\mid\,n}ef$

$=\,\sum_{e\,\mid\,m}e\,\sum_{f\,\mid\,n}f$

$=\,\sigma(m)\sigma(n)$

Next, not that if $p$ is a prime and $k$ a positive integer, $\sigma(p^k)=1+p+p^2+\cdots+p^k=\frac{p^{k+1}-1}{p-1}.$

Combining the two results established above gives the required formula for the sum-of-factors function $\sigma.$ (Cool)