Problem

Source: First Saudi Arabia JBMO TST 2018, P4

Tags: number theory



Let $n=>2$ be a natural number. A set $S$ of natural numbers is called $complete$ if, for any integer $0<=x<n$, there is a subset of $S$ with the property that the remainder of the division by $n$ of the sum of the elements in the subset is $x$. The sum of the elements of the empty set is considered to be $0$. Show that if a set $S$ is $complete$, then there is a subset of $S$ which has at most $n-1$ elements and which is still $complete$.