Pigeonhole riddle
Number Theory
Level
3
In a collection of integers, at least how many are congruent modulo ?
The answer is 2.
This section requires Javascript.
You are seeing this because something didn't load right. We suggest you, (a) try
refreshing the page, (b) enabling javascript if it is disabled on your browser and,
finally, (c)
loading the
non-javascript version of this page
. We're sorry about the hassle.
1 solution
For modulo n , there are exactly n residues, namely 0 , 1 , 2 , 3 , … , n − 1 . If there are n + 1 numbers, at least 2 of the resudes are repeated and hence at least 2 numbers are congruent.