Using the pigeonhole principle, prove that among any n+ 1 integers you can find two integers so that their difference is divisible by n. You will want the “holes” to be the remainder when you divide a value by n.

  • 1
    $\begingroup$ you can look at: math.stackexchange.com/questions/958636/… $\endgroup$
    – BinyaminR
    Aug 22, 2020 at 20:07
  • $\begingroup$ Your question is phrased as an isolated problem, without any further information or context. This does not match many users' quality standards, so it may attract downvotes, or be closed. To prevent that, please edit the question. This will help you recognise and resolve the issues. Concretely: please provide context, and include your work and thoughts on the problem. These changes can help in formulating more appropriate answers. $\endgroup$
    – KReiser
    Aug 22, 2020 at 20:20
  • $\begingroup$ So $n+1$ pigeons and $n$ holes. Sounds good. $\endgroup$ Aug 22, 2020 at 20:21

1 Answer 1


Consider the set $A$ with $3$ numbers. The possible differences are $3$.

If $A$ contains all even or all odd, the differences are all even. If it contains 1 even and two odd or if it contains 1 odd and two even 1 difference is even.

A similar claim can be made if $A$ contains $4$ numbers and the possible differences are $6$. The original $4$ numbers can give a remainder of $0,1,2$ when divided by $3$. Differences contain at least $1$ case when the remainder is $0$, because $A$ contains $6$ elements.

If $A$ has $n+1$ numbers, the possible pairs are $d=\frac{n(n+1)}{2}$.

The possible differences are $d$ as well.

The elements in $A$ can have remainders $0,1,2,\ldots,n-1$ when divided by $n$ and when subtracting there is at least $1$ who has remainder $0$, that means that is divisible by $n$.

Hope this is clear.


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