IMO 2002 · Problem 4

The positive divisors of the integer \(n > 1\) are \(d_1 < d_2 < \ldots < d_k\), so that \(d_1 = 1, d_k = n\). Let \(d = d_1d_2 + d_2d_3 + \cdots + d_{k-1}d_k\). Show that \(d < n^2\) and find all \(n\) for which \(d\) divides \(n^2\).

Official text of the problem. Official problem paper (PDF)

Answer

Exactly all prime numbers \(n\).

Solution

For each \(i=1,\ldots,k-1\), the numbers \(n/d_i\) and \(n/d_{i+1}\) are distinct integers, so \[ \frac{n}{d_i}-\frac{n}{d_{i+1}}\ge 1. \] Multiplying by \(d_id_{i+1}\) gives \[ d_id_{i+1}\le n(d_{i+1}-d_i). \] Summing these inequalities, we obtain \[ d\le n\sum_{i=1}^{k-1}(d_{i+1}-d_i) =n(n-1)<n^2. \]

Now suppose that \(d\mid n^2\), and let \(p\) be the smallest prime divisor of \(n\). The largest proper divisor of \(n\) is \(n/p\): indeed, for any proper divisor \(a\), the integer \(n/a>1\) divides \(n\), hence is at least \(p\). Thus \(d_{k-1}=n/p\).

If \(n\) is composite, then \(k\ge3\), so the sum defining \(d\) contains positive terms besides its last term. Consequently, \[ d>d_{k-1}d_k=\frac{n^2}{p}. \] Together with \(d<n^2\), this shows that the integer \[ m=\frac{n^2}{d} \] satisfies \(1<m<p\). But any prime divisor \(q\) of \(m\) divides \(n^2\), and therefore divides \(n\). By the choice of \(p\), we have \(q\ge p\), contradicting \(q\le m<p\). Hence \(n\) must be prime.

Conversely, if \(n\) is prime, its only positive divisors are \(1,n\), so \(d=n\), which divides \(n^2\). This proves the claimed characterization.

The solution was checked against Evan Chen's published IMO solution notes.