Exercise 331Combinatorics › Pigeonhole principleL1Added 31 Oct 2026

Pigeonhole modulo 4

#pigeonhole#congruences

Statement

Show that among any five integers, there are two whose difference is divisible by $4$ .

Hint

Sort the integers by their remainder when divided by $4$ .

Show solutionHide solution

Every integer has a remainder in $\{0,1,2,3\}$ when divided by $4$ . These are $4$ possible remainders ("boxes") for $5$ integers.

By the pigeonhole principle, two of the integers have the same remainder. If $a=4q+r$ and $b=4q'+r$ , then $a-b=4(q-q')$ is divisible by $4$ .