Writeup: IMO Shortlist 2002 N2

29 Apr, 2025

Problem Statement

Let $n \geq 2$ be a positive integer, with divisors $1 = d_{1} < d_{2} < \dots < d_{k} = n$ . Prove that $S = d_{1} d_{2} + d_{2} d_{3} + \dots + d_{k - 1} d_{k}$ is always less than $n^{2}$ , and determine when it is a divisor of $n^{2}$ .

My Solution

Fun problem that took me way longer that I should have! First, let's start with the second part:

Note that $S \geq d_{k} d_{k - 1} = \frac{n^{2}}{p}$ , where $p$ is the smallest prime divisor of $n$ . We know that $n^{2}$ 's largest divisor besides $n^{2}$ is $\frac{n^{2}}{p}$ , so if $S \geq \frac{n^{2}}{p}$ and $S < n^{2}$ , then we can only have $S | n^{2}$ if $S = d_{k} d_{k - 1}$ , i.e. $S$ has two divisors and therefore $S$ is prime. If we can prove $S < n^{2}$ , then we have successfully proven that $S | n^{2}$ iff $n$ is prime.

Now, we prove $S < n^{2}$ . Note that

\frac{S}{n^{2}} = \frac{1}{d_{k} d_{k - 1}} + \dots + \frac{1}{d_{2} d_{1}} \leq \sum_{i = 1} k - 1 \frac{1}{i (i + 1)} = 1 - \frac{1}{k} < 1

so $S < n^{2}$ and we're done.