Maths Olympiad Prep

Library / /369 of 520

Number theory Difficulty 7.2 National olympiad, round 2 Prove it

Let nn be a positive integer. Let σ(n)\sigma(n) be the sum of the natural divisors dd of nn (including 11 and nn). We say that an integer m1m \geq 1 is superabundant (P.Erdos, 19441944) if k{1,2,,m1}\forall k \in \{1, 2, \dots , m - 1 \}, σ(m)m>σ(k)k.\frac{\sigma(m)}{m} >\frac{\sigma(k)}{k}.
Prove that there exists an infinity of superabundant numbers.

Solution

1. Define the function f(n)=σ(n)n f(n) = \frac{\sigma(n)}{n} , where σ(n)\sigma(n) is the sum of the natural divisors of nn.
2. We need to show that there are infinitely many integers mm such that k{1,2,,m1} \forall k \in \{1, 2, \dots, m-1\} , σ(m)m>σ(k)k \frac{\sigma(m)}{m} > \frac{\sigma(k)}{k} . These integers mm are called superabundant numbers.
3. Consider the product i=1(1+1pi) \prod_{i=1}^\infty \left(1 + \frac{1}{p_i}\right) , where pip_i denotes the ii-th prime number.
4. We claim that this product diverges. To see why, note that:
i=1(1+1pi)1+1p1+1p2+1p3+ \prod_{i=1}^\infty \left(1 + \frac{1}{p_i}\right) \geq 1 + \frac{1}{p_1} + \frac{1}{p_2} + \frac{1}{p_3} + \cdots
5. It is a well-known result that the sum of the reciprocals of the primes diverges. Specifically, the series i=11pi \sum_{i=1}^\infty \frac{1}{p_i} diverges.
6. Since the product i=1(1+1pi) \prod_{i=1}^\infty \left(1 + \frac{1}{p_i}\right) diverges, the function f(n) f(n) can get arbitrarily large.
7. To see why f(n) f(n) can get arbitrarily large, consider the values of f f at products of distinct primes:
f(p1)=1+1p1,f(p1p2)=(1+1p1)(1+1p2),f(p1p2p3)=(1+1p1)(1+1p2)(1+1p3),and so on. f(p_1) = 1 + \frac{1}{p_1}, \quad f(p_1 p_2) = \left(1 + \frac{1}{p_1}\right)\left(1 + \frac{1}{p_2}\right), \quad f(p_1 p_2 p_3) = \left(1 + \frac{1}{p_1}\right)\left(1 + \frac{1}{p_2}\right)\left(1 + \frac{1}{p_3}\right), \quad \text{and so on.}
8. Since the product i=1(1+1pi) \prod_{i=1}^\infty \left(1 + \frac{1}{p_i}\right) diverges, f(n) f(n) can become arbitrarily large.
9. Because f(n) f(n) can become arbitrarily large, it must achieve a new maximum infinitely often. Each time f(n) f(n) achieves a new maximum, the corresponding n n is a superabundant number.

\blacksquare

Want a route through all this instead of an archive? The track puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.

Source: NuminaMath-1.5, licensed Apache-2.0. Statement and solution reproduced as published; topic and difficulty added by this site.