Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

How can we prove with the pigeonhole principle that having $100$ whole numbers, one can choose $15$ of them so that the difference of any $2$ is divisible by $7$?

share|cite|improve this question
Hint: consider remainders upon dividing by 7. – vadim123 Sep 3 '13 at 4:26
And $100 / 7 > 14$. – ShreevatsaR Sep 3 '13 at 4:34

Let $S$ be a set of $100$ integer numbers. Dividing each element of $S$ by $7$ we will get a new set $S'$ with residues modulo $7$ elements. Next, we divide that new set $S'$ into $7$ subsets, where each subset contains $14$ elements with the same residue modulo $7$. If we can't find such division into $7$ sets, then we are done(why?). Since $7\cdot 14=98$, we left with two elements, by taking one of them and putting in the suitable set(of the seven), we get a set of $15$ numbers with same residue modulo $7$.

share|cite|improve this answer

Let the pigeonholes consist of the remainders after division by 7. Let the pigeons be the 100 numbers. By the generalized PHP, some pigeonhole must have at least $$\left\lceil \frac{100}{7}\right\rceil = 15$$ pigeons. These 15 numbers all have the same remainder upon division by 7; hence the difference of any pair is a multiple of 7.

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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