# $19$ divides $ax+by+cz$

Let $X$ be a subset of $\{1,2,\ldots,19\}$ with $|X|=10$. Is it true that there exist $a,b,c,x,y,z \in X$ (not necessarily distinct) such that $19$ divides $ax+by+cz$?

#### Solutions Collecting From Web of "$19$ divides $ax+by+cz$"

Yes, this is true.

Clearly if $19 \in X$ we can just choose $x=y=z=19$ and $a,b,c$ arbitrarily. So we only need to consider the case where $19 \not\in X$.

Since $19$ is prime, we have that all numbers not divisible by $19$ are invertible, that is for any such $a$ we can find a number $b$ such that the product $ab \equiv 1 \bmod 19$. In particular we can find $8$ distinct inverse pairs of numbers within the set $\{1,2,\ldots,18\}$, with two self-inverse numbers:$\{(1), (2,10), (3, 13), (4,5), (6,16), (7,11), (8,12), (9,17), (14,15), (18)\}$

It is also true that for any other number in the set, say $7$, we can find a $b$ for any $a$ in the set such that $ab \equiv 7 \bmod 19$. This number is simply $7a^{-1}$ taken $\bmod 19$. Again such numbers form either distinct pairs in the set or the target number is achieved by a squaring operation. [This follows from considering the operation of a primitive root ($2$ is an example) which generates the set by repeated multiplication]

Then our task is simply to choose $3$ numbers that sum to $19$, say $\{4,7,8\}$, and find the members of $X$ that allow us to form each of these residues $\bmod 19$. Because in each there will be $8$ or $9$ pairs of numbers that multiply together to form that residue, or single numbers that can form it squared, and we have $10$ members of $\{1,2,\ldots,18\}$ in $X$, we know by the pigeonhole principle that we have at least one generation option available to us in $X$.

It is also apparent from this argument that we do not need the third term; we can choose $a,b,x,y$ from $X$ to make $ax+by$ divisible by $19$ also.

Following discussion on the generalized question, I came back to this question to establish how small $|X|$ could be in order to assure that some $a,b,c,x,y,z$ could be chosen from $\{1,2,\ldots,18\}$ to make $ax+by+cz$ divisible by $19$.

Sets where such a selection is possible I called qualifying sets.

Review of all possible sets with $|X|=2$ showed that just under half, $72$ out of $153$, are qualifying sets. Review of sets with $|X|=3$ showed that there were $90$ sets (of $816$ total) that did not contain a qualifying subset of size $2$. Of these $90$, $81$ were qualifying sets using calculations that involved all three elements. The $9$ non-qualifying sets with $|X|=3$ are:

$$\{ 1, 4, 15\} \\ \{ 1, 10, 12\} \\ \{ 2, 8, 11\} \\ \{ 2, 9, 10\} \\ \{ 3, 4, 15\} \\ \{ 3, 11, 17\} \\ \{ 6, 8, 11\} \\ \{ 7, 9, 10\} \\ \{ 11, 15, 18\} \\$$

It is simple to see that no non-qualifying set with $|X|=4$ can be constructed which has all non-qualifying size-3 subsets. So we can substitute “$|X|=4$” for “$|X|=10$” in the original statement and it still holds.