4
$\begingroup$

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?

$\endgroup$
  • 1
    $\begingroup$ It's the same as saying every set of three integers, there are two whose difference is even. You can write down numbers that have nothing to do with "2" but the fact that you chose three of them makes it happen anyway. $\endgroup$ – Gregory Grant May 25 '15 at 16:42
  • 1
    $\begingroup$ Fermat's little theorem tells us that $10^{13}-10$ and $89^{13}-89$ must both be multiples of $13$. So not only do your sets contain a common difference which is a multiple of $13$, we can even be sure of which one it is... $\endgroup$ – Micah May 25 '15 at 16:43
  • 1
    $\begingroup$ I fail to see the problem. If there are only 13 different remainders, it is hard to come up with a different 14-th. $\endgroup$ – mvw May 25 '15 at 16:45
  • $\begingroup$ @GregoryGrant I see, it's a generalization of that. $\endgroup$ – shinzou May 25 '15 at 16:47
  • 1
    $\begingroup$ @kuhaku Yes, it's an exact generalization of that fact. If you write down four numbers, some pair must have difference divisible by $3$. There's nothing magic about $13$ here. $\endgroup$ – Gregory Grant May 25 '15 at 16:49
4
$\begingroup$

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.

$\endgroup$
2
$\begingroup$

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

$\endgroup$
1
$\begingroup$

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.

$\endgroup$
1
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.