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?
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!