Hit by PHP (Pigeon hole principle)

Problem: For coprime a and b, a/b has period of reccurance of length atmost b-1.

This next one is a classic.
Let there be n integers not necessarily distinct.Prove that we pick k (< (n+1)) integers which is divisible by n.

Let i_1, i_2,..., i_n be the integers.

Let a_1=i_1,
a_2=i_1 + i_2
.
.
a_n=i_1+..+i_n

If one of the a_j ( j=1,..,n ) is divisible by n we are done,else by php we can find a_r and a_s (r>s)giving same remainder. Then a_r-a_s gives rem 0 and we are done.