Maths WorkshopMaths problems with full solutions
Exercise 1106Combinatorics › Pigeonhole principleOlympiadAdded 3 Nov 2026

Remainders of consecutive integers

#pigeonhole#remainders#consecutive

Statement

Show that among any n+1n+1 positive integers, two have remainders mod nn differing by exactly 11 or summing to nn ... hmm, this is vague. Better: among any n+1n+1 integers, two have the same remainder mod nn.

Hint

Same as before.

Show solutionHide solution

Solution

Residues. nn possible residues.

Pigeonhole. n+1n+1 integers, nn residues: two same.

Conclusion. They differ by a multiple of nn.