43rd IMO shortlist 2002/N5 solution

43rd IMO 2002 shortlist

Problem N5

m, n are integers > 1. a₁, a₂, ... , a_n are integers, and none is a multiple of m^n-1. Show that there are integers e_i, not all zero, with |e_i| < m, such that e₁a₁ + e₂a₂ + ... + e_na_n is a multiple of mⁿ.

Solution
Put N = mⁿ. Let X be the set of all (b₁, b₂, ... , b_n), where b_i are non-negative integers < m. Evidently X has N elements. Define f(b₁, b₂, ... , b_n) = the residue of a₁b₁ + a₂b₂ + ... + a_nb_n mod N. If any two distinct elements B = (b₁, b₂, ... , b_n) and C = (c₁, c₂, ... , c_n) of X have f(B) = f(C), then we are home, taking e_i = b_i - c_i.

So it is sufficient to show that there must be two such elements. If not, then the set of all f(B) as B ranges over X is just {0, 1, 2, ... , N-1}. Let w be a primitive Nth root of unity. Take the sum of w^f(B) over all elements B of X. It is 1 + w + w² + ... + w^N-1 = 0. On the other hand, it is the product of n terms (1 + w_i + w_i² + ... + w_i^m-1), where w_i = w to the power of a_i. The term can be written as (1 - w_i^m)/(1-w_i), which is non-zero because a_i is not a multiple of m^n-1 and so maⁱ is not a multiple of N. So zero is a product of non-zero terms. Contradiction.

43rd IMO shortlist 2002