IMO 2002 SL N5

Origin: IRN | Category: Number Theory

Problem

Let m, n \geq2 be positive integers, and let a1, a2, . . . , an be integers, none of which is a multiple of mn−1. Show that there exist integers e1, e2, . . . , en, not all zero, with |ei| < m for all i, such that e1a1 + e2a2 + \cdot \cdot \cdot + enan is a multiple of mn.

Solution

Consider all possible sums c1a1 + c2a2 + \cdot \cdot \cdot + cnan, where each ci is an integer with 0 \leqci < m. There are mn such sums, and if any two of them give the same remainder modulo mn, say  ciai \equiv diai (mod mn), then (ci −di)ai is divisible by mn, and since |ci −di| < m, we are done. We claim that two such sums must exist. Suppose to the contrary that the sums  i ciai (0 \leqci < m) give all the different remainders modulo mn. Consider the polynomial P(x) =  xc1a1+\cdot\cdot\cdot+cnan, where the sum is taken over all (c1, . . . , cn) with 0 \leqci < m. If \xi is a primitive mnth root of unity, then by the assumption we have P(\xi) = 1 + \xi + \cdot \cdot \cdot + \ximn−1 = 0. On the other hand, P(x) can be factored as P(x) = n

i=1 (1 + xai + \cdot \cdot \cdot + x(m−1)ai) = n

i=1 1 −xmai 1 −xai , so that none of its factors is zero at x = \xi because mai is not divisible by mn. This is obviously a contradiction. Remark. The example ai = mi−1 for i = 1, . . . , n shows that the condition that no ai is a multiple of mn−1 cannot be removed.