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

Question

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:

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

Answer 1

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.