Difference divisible by $n$

#pigeonhole#difference#divisibility

Statement

Show that among any $n+1$ integers, two have difference divisible by $n$ .

Hint

Look at residues modulo $n$ .

Show solutionHide solution

Residues. There are $n$ residue classes modulo $n$ .

Pigeonhole. With $n+1$ integers and $n$ residue classes, two have the same residue.

Conclusion. Their difference is divisible by $n$ .