In every set of $14$ integers there are two that their difference is divisible by $13$

Question

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?

Answer 1

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.

Answer 2

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$.

Answer 3

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.

Answer 4

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.