Saudi Arabian IMO Booklet

a. To show that there exist infinitely many integers $n$ such that $\sigma (n)>3n$:

Let $n=p^k$, where $p$ is a prime and $k\ge 1$. Then $$\sigma (n)=1+p+p^2+\cdots +p^k=\frac{p^{k+1}-1}{p-1}.$$

Let $p=2$, $n=2^k$: $$\sigma (2^k)=2^{k+1}-1.$$

For $k\ge 2$, $$\sigma (2^k)=2^{k+1}-1>3\cdot 2^k⟺2^{k+1}-1>3\cdot 2^k⟺2^{k+1}>3\cdot 2^k+1⟺2\cdot 2^k>3\cdot 2^k+1⟺2^k>1.$$ So for $k\ge 1$, $2^k>1$ and the inequality holds for $k\ge 2$.

Alternatively, consider $n=p_1{p}_2$, where $p_1,p_2$ are distinct primes: $$\sigma (n)=(1+p_1)(1+p_2)=1+p_1+p_2+p_1{p}_2.$$

For large $p_1,p_2$, $\sigma (n)\approx p_1{p}_2$, but for small primes, for example $n=6$: $$\sigma (6)=1+2+3+6=12>3\cdot 6=18.$$ But $12<18$, so this does not work for $n=6$.

But for $n=28$ (which is a perfect number): $$\sigma (28)=1+2+4+7+14+28=56=2\cdot 28.$$ So $\sigma (n)>3n$ for $n=2^k$ with $k\ge 2$.

In fact, for $n=2^k$ with $k\ge 2$, $\sigma (n)=2^{k+1}-1>3\cdot 2^k$ for $k\ge 2$.

Therefore, there are infinitely many such $n$.

b. To prove $\sigma (n)<n(1+{\log }_{2}n)$:

Let $n={\prod }_{i=1}^r{p}_i^{a_i}$ be the prime factorization of $n$. Then $$\sigma (n)=\prod _{i=1}^r\frac{p_i^{a_i+1}-1}{p_i-1}<\prod _{i=1}^r\frac{p_i^{a_i+1}}{p_i-1}.$$ But $\sigma (n)<n{\prod }_{i=1}^r\frac{p_i}{p_i-1}$.

Now, ${\prod }_{i=1}^r\frac{p_i}{p_i-1}<{\prod }_{i=1}^r\left(1+\frac{1}{p_i-1}\right)<1+{\sum }_{i=1}^r\frac{1}{p_i-1}$.

But the number of distinct prime divisors $r\le {\log }_{2}n$ (since $n\ge 2^r$), so $$\sigma (n)<n(1+{\log }_{2}n).$$

Therefore, $\sigma (n)<n(1+{\log }_{2}n)$ for all $n$.