# sum of factors

• Jun 24th 2009, 08:03 AM
jashansinghal
sum of factors
What is the sum of all factors of 45000 which are divisible by 10
• Jun 24th 2009, 09:38 AM
TheAbstractionist
That would be 10 times the sum of all the factors of 4500. The sum-of-factors function $\displaystyle \sigma$ has the following property: if $\displaystyle n=p_1^{k_1}\cdots p_r^{k_r}$ where the $\displaystyle p_i$ are distinct primes, then

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

Thus $\displaystyle \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.
• Jun 25th 2009, 01:30 AM
jashansinghal
can u give an easy method
• Jun 25th 2009, 06:23 AM
TheAbstractionist
I don’t see anything wrong with the proof, particularly the formula

$\displaystyle \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 $\displaystyle \gcd(m,n)=1$ then $\displaystyle \sigma(mn)=\sigma(m)\sigma(n).$ Note that a divisor $\displaystyle d$ of $\displaystyle mn$ can be written as $\displaystyle d=ef$ where $\displaystyle e\mid m$ and $\displaystyle f\mid n$ and $\displaystyle \gcd(e,f)=1.$ Hence

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

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

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

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

Next, not that if $\displaystyle p$ is a prime and $\displaystyle k$ a positive integer, $\displaystyle \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 $\displaystyle \sigma.$ (Cool)