Maths Olympiad Prep

Library / /77 of 158

Number theory Difficulty 5.7 AIME, harder Prove it Estonia

Denote the number of all positive divisors of a positive integer nn by δ(n)\delta(n) and the sum of all positive divisors of a positive integer nn by σ(n)\sigma(n). Prove that σ(n)>δ(n)22\sigma(n) > \frac{\delta(n)^2}{2}.

Solutions — 2

Solution 1

Let a1,a2,,aδ(n)a_1, a_2, \dots, a_{\delta(n)} be the positive divisors of nn in increasing order. We obtain
σ(n)=a1+a2++aδ(n)1+2++δ(n)=δ(n)(δ(n)+1)2>δ(n)22. \sigma(n) = a_1 + a_2 + \dots + a_{\delta(n)} \ge 1 + 2 + \dots + \delta(n) = \frac{\delta(n) \cdot (\delta(n)+1)}{2} > \frac{\delta(n)^2}{2}.

Solution 2

For every positive divisor dd of a positive integer nn, d+nd2dnd=2nd + \frac{n}{d} \ge 2\sqrt{d \cdot \frac{n}{d}} = 2\sqrt{n}. Thereby if dnd \ne \sqrt{n}, the inequality is strict. If nn is not a perfect square, then by adding all these inequalities for divisors d<nd < \sqrt{n} leads to
σ(n)>δ(n)22n=δ(n)n, \sigma(n) > \frac{\delta(n)}{2} \cdot 2\sqrt{n} = \delta(n)\sqrt{n},
since every divisor of nn occurs exactly once in a pair (d,nd)(d, \frac{n}{d}). If nn is a perfect square, then analogously
σ(n)δ(n)122n+n=δ(n)n. \sigma(n) \ge \frac{\delta(n)-1}{2} \cdot 2\sqrt{n} + \sqrt{n} = \delta(n)\sqrt{n}.
On the other hand, if nn is not a perfect square then the number of pairs (d,nd)(d, \frac{n}{d}) where d<nd < \sqrt{n}, is less than n\sqrt{n}, whence n>δ(n)2\sqrt{n} > \frac{\delta(n)}{2}. If nn is a perfect square then the number of such pairs is at most n1\sqrt{n}-1, which gives n1δ(n)12\sqrt{n}-1 \ge \frac{\delta(n)-1}{2} implying n>δ(n)2\sqrt{n} > \frac{\delta(n)}{2} again. Hence,
σ(n)δ(n)n>δ(n)δ(n)2=δ(n)22. \sigma(n) \ge \delta(n)\sqrt{n} > \delta(n) \cdot \frac{\delta(n)}{2} = \frac{\delta(n)^2}{2}.

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: MathNet, licensed CC-BY-4.0. Statement reproduced verbatim; metadata (topic, difficulty) added by this project.