1

I am trying to understand how to prove a Statement using the pigeonhole principle.

Prove the following result using the pigeon-hole principle. In every collection of 7 integers there are at least two whose difference is divisible by 6. any ideas? thanks in advance

Samir Fahel
  • 15
  • Use the fact that for every $3$ consecutive integers, one will be divisible by $3$ and for every $2$ consecutive integers one will be even and divisible by $2$. – JohnColtraneisJC Nov 29 '17 at 14:28
  • 3
    Hint: there are exactly $6$ possible remainders on division by six. If you have seven integers, then at least two have to have the same remainder. – lulu Nov 29 '17 at 14:28

3 Answers3

1

Consider the residues of the 7 numbers when divided by 6 (their classes modulo 6). There are 6 possible residues, so one must be used twice, by the pigeonhole principle. The difference of the corresponding original integers is a multiple of 6.

Reiner Martin
  • 4,097
1

There are six possible remainders modulo 6: those are $0, 1, 2, 3, 4, 5$.

Since there are $7$ integers in your set, by the pigeonhole principle there will be at least two of them with the same remainder modulo 6. Their difference will then be divisible by $6$.

mechanodroid
  • 46,490
1

By the remainder's theorem, every integer number divided by $6$ is of the form: $$n=6q+r$$ where $0 \leq r < 6$

Since there are $6$ possible remainders, while you have $7$ numbers, at least two numbers must have the same remainder divided by $6$. Therefore, the difference of these two numbers must be divisible by $6$.

stressed out
  • 8,130