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

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.

• You definitely don't need that the sequence is increasing... Dec 7, 2015 at 7:48
• @ThomasAndrews Yeah... That was in a question set... It doesn't matter if the sequence is increasing or not... The logic would be the same... Anyway, I'll edit it... Dec 7, 2015 at 7:50

$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$.
• You can leave out $0$. If that counted then the question is trivial since $n$ divides $0$. Leaving it out, there is either a reside hit twice, or the residue $0$ is still hit somewhere. Dec 7, 2015 at 7:51