Prove that in every set of $14$ integers there are two that their difference is divisible by $13$
The proof goes like this, there are $13$ remainders by dividing by $13$, there are $14$ numbers so from the pigeon hole principle, there are two that have the same remainder so their difference is divisible by $13$.
But what if we'll take a set of numbers that has nothing in common with $13$?
Like $\{10,10^2,10^3…,10^{14}\}$ or a prime that's further away from 13: $\{89,89^2,…,89^{14}\}$ how is it possible that those numbers and their differences have something in common with a totally different prime?
Best Answer
Consider your selected numbers $\{a_1, a_2, \ldots a_{14}\} \bmod 13$. Then they must each be in a residue class, $\{r_1, r_2, \ldots r_{14}\} $ - but there are only $13$ residue classes, so at least $2$ must be in the same class. The difference of any $2$ numbers in the same residue class is divisible by $13$.
Note that by using prime powers different to $13$, you are avoiding the $0$ residue class, so there will actually be at least $2$ differences divisible by $13$ in that case, as there are only $12$ clases being occupied by the $14$ numbers.