A non-dividing set is no larger than any of its elements

Let $A$ be a finite non-dividing set of natural numbers and let $a\in A$ with $a>0$. Then

Since this holds for every element, it holds for the smallest one, so $|A|\le\min A$: a non-dividing set can never be larger than its least element.

The proof is a pigeonhole argument on prefix sums. List $A\setminus\{a\}$ in any order as $x_1,\ldots,x_{m}$ and form the partial sums $p_0=0$, $p_i=x_1+\cdots+x_i$. If $|A|>a$ there are at least $a+1$ such partial sums, so two of them are congruent modulo $a$; their difference is the sum of a nonempty contiguous block $x_{i+1}+\cdots+x_j$, which is a sum over a nonempty subset of $A\setminus\{a\}$ divisible by $a$, contradicting the non-dividing property.

This is the elementary first bound on the extremal function $F(N)$ of Erdős problem #131; the much stronger $F(N)<3N^{1/2}+1$ is due to Erdős, Lev, Rauzy, Sándor and Sárközy.

Formalization Note. The hypothesis $a>0$ is needed: the singleton $\{0\}$ is vacuously non-dividing and has cardinality $1>0$. In the setting of the problem, where $A\subseteq\{1,\ldots,N\}$, positivity is automatic.