Given any five integers, there will be two that have a sum or difference divisible by 7. I'm trying to solve this using the Pigeonhole Principle, but it is not making sense to me, how this principle holds true in this case. Aren't the "pigeons" in this case "five" and the "holes" are "seven"? I'm so confused.

  • 2
    $\begingroup$ Hint: How many sums are possible? How many differences are possible? $\endgroup$
    – JoshuaZ
    Oct 24, 2018 at 2:40
  • 1
    $\begingroup$ The 7 holes are not $0,1,2,3,4,5,6,7$. The 4 holes are $0, \pm 1, \pm 2, \pm 3$ $\endgroup$
    – fleablood
    Oct 24, 2018 at 6:39

3 Answers 3


consider $a_n = x_n \mod 7$ In order to avoid a difference divisible by 7, all 5 $a_n$ must be distinct.

In order to avoid a sum divisible by 7, no two $a_n$ can sum to 7

So we actually have only 4 holes in which to put our 5 $a_n$

1) $a_n=0$

2) $a_n = 1 $ or $a_n = 6$

3) $a_n = 2 $ or $a_n = 5$

4) $a_n = 3 $ or $a_n = 4$

To avoid a sum or difference divisible by 7 we would need to put 5 integers into 4 holes with no more than one in each hole. This can't be done, therefore having at least one pair whose sum or difference is divisible by 7 is unavoidable.


Here is another argument which is based on the following fact:

  • There are only $4$ quadratic remainders $\mod 7$: $0,1,2,4$.

Now, let $a_1, \ldots , a_5 \in \mathbb{Z}$.

  • There is $1\leq k < l \leq 5$ such that

$$a_k^2 \equiv a_l^2 \mod 7 \Rightarrow (a_k + a_l)(a_k - a_l) \equiv 0 \mod 7$$ This proves the claim.

  • $\begingroup$ Why argue by contradiction? If two integers have equal quadratic remainder, then either their sum or their difference is a multiple of 7, and you are done. $\endgroup$ Oct 24, 2018 at 4:36
  • $\begingroup$ @ Andrés E. Caicedo: Ha!. That's right. It's still early here in the morning. Will edit it accordingly. :-) Thanks. $\endgroup$ Oct 24, 2018 at 4:44

Note every integer $a$ is such that $a \equiv 0, \pm 1, \pm 2, \pm 3 \pmod 7$.

Let the pigeons be the $5$ integers. Let $k = 0, 1, 2, 3$ be the $4$ holes.

We assign pigeons to holes:

We assign pigeon $a$ the hole $k$ if $a \equiv \pm k \pmod 7$.

Two pigeons must share the same hole:

There are five pigeons so we are going to have two pigeons, $a$ and $b$ in the same hole, $k$. i.e. $a \equiv \pm k \pmod 7$ and $b \equiv \pm k \pmod 7$.

which means:

So $a \equiv \pm b \pmod 7$. So $a \mp b \equiv 0 \pmod 7$. So either $a + b$ is divisible by $7$ or $a-b$ is divisible by $7$.



Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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