How do I prove that among any $5$ integers, you are able to find $3$ such that their sum is divisible by $3$? How do I prove that among any $5$ integers, you are able to find $3$ such that their sum is divisible by $3?$
I realize that this is a number theory question and we use modular arithmetic, but I'm unsure of where to begin with this specific situation.
 A: Consider the residue class modulo $3$ of each of the five numbers. If three of them are equal, then the numbers corresponding to them will work. Otherwise, no three numbers have equal residue classes, but there are only $3$ potential residue classes, and that means that all three actually occur. The numbers corresponding to these classes work. 
A: All the integers can be represented as $3n+1, 3n+2$ or $3n; n \in \mathbb{Z}$. Among the five integers, if there is at least one integer of each form, then their sum would be divisible by $3$, as $3a+(3b+1)+(3c+2)=3(a+b+c)+3 \equiv 0 \, (\mathrm{mod} \; 3)$
If there isn't, all the numbers are of the remaining two forms. So, there are at least three integers of the same form, which is obvious using the pigeon hole principle. Their sum would be divisible by 3 as $(3a+i)+(3b+i)+(3c+i)=3(a+b+c+i)\equiv 0 \, (\mathrm{mod} \; 3);i =0,1,2$ Thus, completing the proof. 
A: Hint: pigeonhole principle. $5$ pigeons (integers) and $3$ pigeonholes (numbers of the form $3n, 3n+1, 3n+2$). This works for $5$ or $4$ distinct integers among the $5$. If $3$ or more integers are the same, then it is trivial since you have 3 times the same number, say $k$, so $k+k+k=3k$ is obviously divisible by $3$ no matter what $k$ was.
A: Consider the remainders of the numbers when divided by 3. Clearly there are only three possible remainders: 0, 1 or 2.


*

*If all these remainders occur among the given numbers, then adding together three numbers with different remainders will yield a sum that is divisible by 3 (since 0 + 1 + 2 = 3).

*Otherwise, at least one of the three remainders does not occur among the five given numbers. By the pigeonhole principle, at least one of the other two remainders must thus occur more than twice (since 5 > 2 × 2). Adding together three numbers with the same remainder will then yield a sum divisible by 3.
A: Consider the following seven numbers:
$a_1\\a_2\\a_3\\a_4\\a_5\\a_1+a_2+a_3+a_4\\a_2+a_3+a_4+a_5$
Since there are seven numbers three of them must have same remainder modulo $3$. If all are from the first five then their sum is multiple of $3$ otherwise one of the four-element-sum and one of its summand must be included and their difference is divisible by $3$.
