Prove that: $$\sigma(n) \leq n(\omega(n) + 1),$$ where: $\sigma(n)$ - sum of divisors function and $\omega(n)$ - number of prime divisors function.
Asked
Active
Viewed 325 times
2
-
Do you know how $\sigma(n)$ depends on the prime factorisation of $n$? – Daniel Fischer Sep 06 '13 at 13:17
1 Answers
3
For
$$n = \prod_{j = 1}^{\omega(n)} p_j^{a_j}$$
with $p_j < p_{j+1}$, we have
$$\frac{\sigma(n)}{n} = \prod_{j=1}^{\omega(n)} \frac{p_j^{a_j+1}-1}{p^{a_j}(p_j-1)} < \prod_{j=1}^{\omega(n)} \frac{p_j}{p_j-1}.$$
Now, since we indexed the primes dividing $n$ in ascending order, we certainly have $p_j \geqslant j+1$, and hence $\frac{p_j}{p_j-1} \leqslant \frac{j+1}{j}$, so
$$\frac{\sigma(n)}{n} < \prod_{j=1}^{\omega(n)} \frac{j+1}{j} = \omega(n)+1.$$
Daniel Fischer
- 206,697
-
Great, my solution is the same! Using similar method You can also show that: $$\sigma(n) < n \cdot 2^{\omega(n)}.$$ – user92813 Sep 06 '13 at 14:27