Exercise 1625Combinatorics › Counting principlesOlympiadAdded 3 Nov 2026

Multiples via pigeonhole

#pigeonhole#multiples#divisibility

Statement

Show that among any $n+1$ integers from $\{0,1,\ldots,n\}$ , two are congruent mod $n$ ? (Trivial since there are $n+1$ values and $n$ residue classes.) Better: among any $n+1$ integers, two have difference divisible by $n$ .

Hint

Consider residues mod $n$ .

Show solutionHide solution

Solution

Pigeonhole. $n+1$ integers and $n$ residue classes mod $n$ : two have the same residue.

Difference. Their difference is divisible by $n$ .

Conclusion. Among any $n+1$ integers, two have difference divisible by $n$ .

Multiples via pigeonhole

Statement

Solution

More problems in Counting principles