Problem
NT-B2-M10-P018 Composite Numbers Have Large Divisor Sum
#18
★★★★★ Level 5 of 5
Prove that if \(n\) is composite, then \(\sigma(n)>n+\sqrt{n}\).
1001 Problems in Classical Number Theory (method inspiration) · Problem 617
Take the smallest divisor \(d>1\).
Let \(d\) be the smallest divisor of \(n\) greater than \(1\). Then \(d\le \sqrt{n}\), otherwise \(n\) would have no divisor between \(1\) and \(\sqrt{n}\). The number \(\frac{n}{d}\) is also a divisor and \(\frac{n}{d}\ge \sqrt{n}\). The divisors \(1,d,\frac{n}{d},n\) contribute at least \(1+d+\frac{n}{d}+n>n+\sqrt{n}\). Hence \(\sigma(n)>n+\sqrt{n}\).
A strong estimate with a short proof.