IMO 2002 SL N2

Origin: ROM | Category: Number Theory

Problem

Let n \geq2 be a positive integer, with divisors 1 = d1 < d2 < \cdot \cdot \cdot < dk = n. Prove that d1d2 + d2d3 + \cdot \cdot \cdot + dk−1dk is always less than n2, and determine when it is a divisor of n2.

Solution

Set S = d1d2 + \cdot \cdot \cdot + dk−1dk. Since di/n = 1/dk+1−i, we have S n2 = dkdk−1 + \cdot \cdot \cdot + d2d1 . Hence d2d1 \leqS n2 \leq  dk−1 −1 dk 

• \cdot \cdot \cdot +  1 d1 −1 d2  = 1 −1 dk < 1, or (since d1 = 1) 1 < n2 S \leqd2. This shows that S < n2. Also, if S is a divisor of n2, then n2/S is a nontrivial divisor of n2 not exceeding d2. But d2 is obviously the least prime divisor of n (and also of n2), so we must have n2/S = d2, which holds if and only if n is prime.