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 \geq 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 \geq 2$,
$$\sigma(2^k) = 2^{k+1} - 1 > 3 \cdot 2^k \iff 2^{k+1} - 1 > 3 \cdot 2^k \iff 2^{k+1} > 3 \cdot 2^k + 1 \iff 2 \cdot 2^k > 3 \cdot 2^k + 1 \iff 2^k > 1.$$
So for $k \geq 1$, $2^k > 1$ and the inequality holds for $k \geq 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 \geq 2$.

In fact, for $n = 2^k$ with $k \geq 2$, $\sigma(n) = 2^{k+1} - 1 > 3 \cdot 2^k$ for $k \geq 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 \leq \log_2 n$ (since $n \geq 2^r$), so
$$\sigma(n) < n (1 + \log_2 n).$$

Therefore, $\sigma(n) < n(1 + \log_2 n)$ for all $n$.