Olson's theorem

From Egres Open
Jump to: navigation, search

Theorem (Olson [1]). Let q be a prime power, and let A be an [math]m \times n[/math] integer matrix, where [math]m \geq (q-1)n+1[/math]. There exists a non-empty subset of the columns of A such that every coordinate of the sum of these columns is divisible by q.

This is actually a special case of a theorem of Olson on finite Abelian groups that appeared in [1].


  1. 1.0 1.1 J.E. Olson, A combinatorial problem on finite Abelian groups I, J. Number Theory 1 (1969) 8-10, DOI link