Thread: Pigeonhole Proof

Prove that for any n+1 integers a1, a2, ..., a(n+1), there exist two of the integers ai and aj with i != j such that ai - aj is divisible by n.

I know the use of the pigeonhole principle is the way to attack this proof. I just don't know how to show it.

Any help is greatly appreciated. Thanks!

Hint - think of remainder when a_i divided by 'n' as holes and a_i's as pigeon.
How many bins you have?
How many pigeons?