# Proof involving the Pigeonhole principle

Prove that among any given $n + 1$ positive integers, there are always two whose difference is divisible by $n$

My Answer:

Using Pigeonhole principle:

From a set of at least $2$ different $n+1$ positive integers the difference between $n+1$ integers will always have a case where it is divisible by $n$. Because if there is $n+1$ integers which can be pigeons in this case then there must be at least $n$ holes where $n+1$ integers can divide by $n$. Although this does not mean all $n+1$ integers can be divisible by $n$ but there are cases where they can be.

Examples:

• $(16 - 13) / 2$ is not divisible by $n$ for $n+1$ integers, where $n = 2$.
• $(15 - 13) / 2 = 1$ is divisible by $n$, where $n = 2$.
• $(13-12) + (16-14) / 4$ is not divisible by $n$, where $n = 4$.

## 1 Answer

While the pigeonhle principle can be used here, the proof you give is not very clear.

Try using as the holes the set of integers mod $n$. Then for each of the $n+1$ given integers $m_k$ create a "pigeon" by mapping $m_k \mapsto (m_k \mod n)$.

Any two $m_k$ with the same values mod $n$ will have a difference divisible by $n$.

Now if no difference is divisible by $n$ you have fit $n+1$ pigeons into $n$ holes, which is a contradiction.

• So basically you used proof by contradiction using pigeonhole principle to show how it can be true because of the final case where no difference can be divisble by n means u can fit n+1 pigeons into n holes which contradicts the pigeonhole principle correct? – geforce Oct 9 '14 at 16:57
• Yes. Some real purist mathematicians dislike proof by contradiction, but when you use the pigeonhole principle it almost always comes down to a proof by contradiction -- "... and there were not enough holes to have done such-and-thus". – Mark Fischler Oct 9 '14 at 16:58
• Ok thanks very much Mark that makes sense. – geforce Oct 9 '14 at 17:00
• @MarkFischler what do 'purist' mathematicians find wrong with proof by contradiction? Is it because it's a little brute force? – Sherlock Holmes Oct 11 '14 at 1:22