I have this algebra problem that I can't work out.
Let $a_1, a_2, a_3, ..., a_n$ be integers. Prove that there exists indexes $i, j$ with $1 \leq i \leq j \leq n $ such that $\sum_{k=i}^{j}a_k$ is divisible by $n$.
I started to look at all possible remainders like this:
Let $x$ be the sum from $i$ to $j$ and $r_l$ the remainders of x (with $l$ from $0$ to $x-1$). I can always find a combination of $j$ and $r_k$ that will divide $x$. So:
$x+j+r_k \equiv 0\ (j+r_k)$
But I can't get passed beyond this intuition, any hints or suggestions are welcome, thanks!
Let $S_j = \displaystyle\sum_{i=1}^j a_i$, $1 \leq j \leq n$. There are $n$ of these sums, and the number of possible remainders on division by $n$ is $n$.
Hence, one of these two must happen:
1) One of the $S_j$ is divisible by $n$ in which case we are done.
2) If no $S_j$ leaves a remainder of $0$, then there are only $n-1$ possible remainders for $S_j$ to take. Hence, by pigenhole principle, some $S_j$ and $S_k$ leave the same remainder when divided by $n$. Then, $S_j - S_k = \displaystyle\sum_{l=k}^j a_l$ is divisible by $n$, hence we are done.
Either way, we are done.
EDIT : As suggested in the comments, we note that given $k \geq n$ integers, by repeating the above argument and noting that there are at least $k$ (instead of $n$) numbers $S_l = \sum_{i=1}^l a_i$ now, definitely two of them have the same remainder upon division by $n$, so the result follows.
However, for $k < n$, it is possible to construct $a_1,...,a_k$ such that $\sum_{i=j}^k a_i$ is not divisible by $n$ for any $j,k$. Indeed, simply take $a_i = 1$ for all $i$, in which case any such sum is strictly between $0$ and $n$, and hence cannot be a multiple of $n$.
This proves the following statement :
Given $k,n \in \mathbb N$, the following are equivalent :
for every $k$ integers $a_1,...,a_k$ there exist $1 \leq j \leq l \leq k$ such that $n$ divides $\sum_{x=j}^l a_x$.
$k \geq n$.