Pigeonhole with numbers

#pigeonhole#numbers#residue

Statement

Show that among any $n+1$ integers, two have the same remainder upon division by $n$ .

Hint

There are $n$ possible remainders.

Show solutionHide solution

Remainders. $\{0,1,\ldots,n-1\}$ : $n$ possibilities.

Pigeonhole. $n+1$ integers, $n$ remainders: two share the same remainder.

Conclusion. They differ by a multiple of $n$ .