In every set of $14$ integers there are two that their difference is divisible by $13$ 
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?
 A: 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.
A: You can break up the set of integers in to $13$ sets which do not intersect.
There are the multiples of of $13$, numbers whose remainder when divided by $13$ is $1$, numbers whose remainder is $2$ and so on.  If you pick $14$ distinct numbers, at least two of them have to belong to set same set by the pigeonhole principle. The difference of these two will be divisible by $13$.
A: I'm glad I now know what the Pigeonhole Principal is after having heard it so many times. :)
There being $14$ distinct numbers$\in N\gt 13$, simply apply the Division Algorithm to get the remainders $0-12$ for $13$ of those numbers.  So produce set $\{13q_0 + r_0,13q_1 + r_1,...,13q_{12}+r_{12}\}$.  Remainders $r_1-r_{12}$ are the numbers $0$ through $12$ and are distinct.  if any were the same the difference would be divisible by $13$ and done.  now the $14th$ number must have the same remainder as one of the other $13$ and so the difference is divisible by $13$.  I actually stumbled on this in an induction proof.  Induction on the range of numbers/greatest number $n$.
Base case $n=14$:must have all numbers $1$ through $14$.  $14-1=13$.
Assume true for $n$.  For $n+1$ can apply what is said above.  If all $14$ chosen from set through range $n$ done/true, by inductive hypothesis.
Otherwise if $n+1$ chosen have set/subset $\{\{i_1,i_2,...,i_{13}\},n+1\}$ and can apply what is said above.  That is, if none of $\{i_1,i_2,...,i_{13}\}$ have same remainder mod $13$ they cover the entire range of remainders mod $13$ and therefore $n+1$ mod $13$ must be same as one of $\{i_1,i_2,...,i_{13}\}$mod $13$.  This completes the induction. (if same mod $13$ difference between the two is divisible by $13$) 
Induction is not needed for this problem, though. 
A: Intuitively, you could think in terms of modular arithmetic: Call 3 members of your set $a,b$ and $c$. Suppose $a-b=k_1 \mod 13$, and  $a-c= k_2 \mod 13$. Now if $k_1=k_2$, then $b-c$ will be divisible by 13, so you need $k_1 \neq k_2$ to have problems. But you have 13 such equations, and only 12 different values for $k$, so apply the pigeonhole principle here and you are done.
