Conditions for a Zero Sum Modulo n

Extract

In this paper the following result is proved.

Let n > 0 and k ≥ 0 be integers with n — 2k ≥ 1. Given any n — k integers

there is a non-empty subset of indices I ⊂ {1, 2,…, n — k} such that the sum Σ_i∊I ≡ 0(mod n) if at most n — 2k of the integers (1) lie in the same residue class modulo n.

The result is best possible if n ≥ 3k — 2 in the sense that if "at most n — 2k" is replaced by "at most n — 2k + 1" the result becomes false. This can be seen by taking a_j = 1 for 1 ≤ j ≤ n — 2k + 1 and a_j = 2 for n —2k + 2 ≤ j ≤ n — k, noting that the number of 2's here is n — k — (n — 2k + 1)= k — 1 ≤ n — 2k + 1.