Show that the sum of a run of integers is divisible by $n$

Question

Here is the problem:

Let $a_1,a_2,...,a_n$ be integers. Show that there exist integers $k$ and $r$ such that the sum $$a_k+a_{k+1}+...+a_{k+r}$$ is divisible by $n$.

My thoughts: I suppose we have to compare the residue of the runs modulo $n$. The pigeon hole principle should be applied too. I to find two runs of integers starting from the same integer with sums congruent modulo $n$ but I've been unable to do so. It'd be great if anyone can help.

Answer 1

We shall look at the sums:

$0\\a_1\\a_1+a_2\\a_1+a_2+a_3\\...\\a_1+a_2+...+a_n$

There are $n+1$ numbers so two of them will have same remainder over $n$ and their difference is a multiple of $n$.