Prove that among any 16 perfect cubes we can always find two cubes whose difference is divisible by 91.
Solution
Notice first that any perfect cube is congruent to either , or modulo and it is congruent to either , , , , or modulo . Because and are relatively prime numbers, by the Chinese Remainder theorem, a perfect cube is congruent to precisely one of different residues modulo . Therefore, by the Pigeonhole principle, we can always find among any perfect cubes, two cubes which are congruent modulo .
Want a route through all this instead of an archive? The track
puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.