# Proof involving the Pigeonhole principle

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

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

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.