# From any given twelve integers, two have a difference that is a multiple of 5

How will you show that from a set of twelve given natural numbers (arbitrary) you can always find two such that their difference is divisible by $5$?

-
Pigeonhole principle; Hint: from any set of six natural numbers you can always find two whose difference is a multiple of $5$. – Arturo Magidin Nov 26 '11 at 4:16
By the way, you should work on your question titles. There are very many problems in mathematics that are something with numbers, and knowing that this one is the second you've asked in quick succession is completely useless for someone who reads the lists of questions. – Henning Makholm Nov 26 '11 at 4:18

Label your twelve numbers $a_1,\dots,a_{12}$, and consider the eleven differences, $a_1-a_2,\dots,a_1-a_{12}$. These eleven elements cannot all be in different congruence classes modulo $5$, since there are only $5$ such congruence classes. So $$a_1-a_i\equiv a_1-a_j\pmod{5}$$ for some distinct $a_i$ and $a_j$. This implies $a_i\equiv a_j\pmod{5}$. That said, $12$ seems a little large, and you can actually conclude this from a set of only $6$ numbers.
@AnamitraPalit: I would suggest learning a bit about modulo arithmetic. In fact, your argument shows that among 11 or more numbers, there are always two whose difference is a multiple of ten (let alone a multiple of five). Six numbers are more than enough to guarantee a difference which is a multiple of $5$. In general, you need $n+1$ to guarantee that there are two whose difference is a multiple of $n$. – Arturo Magidin Nov 26 '11 at 5:11
Suppose, your numbers are $a_1,a_2,\ldots,a_{12}$. Divide each number by 5 and collect their remainders as $r_1, r_2 , r_3,\ldots, r_{12}$. As each $r_i$ satisfies $0\leq r_i\leq 4$ for each $i$, $1\leq i\leq 12$, there always exists at least two $r_i$'s, say $r_j$ and $r_k$, having same remainders. Take corresponding numbers $a_j$ and $a_k$. Since, $r_j=r_k$, it implies $a_j \bmod 5= a_k \bmod 5$, which further implies $(a_j-a_k) \bmod5=0$; i.e. there difference is divisible by 5. proved :)