So I'm confused and stuck on how to approach this question. Any direction in the right path would be greatly appreciated.

Let $n\in N$. Prove that any sequence of $n$ integers $a_1, a_2, \ldots,a_n$ (no restriction on whether they are positive or negative, repetition is also possible), there exists a non-empty subsequence of consecutive integers such that their sum is divisible by $n$. This subsequence could have any length from $1$ to $n$. In other words, there exists two integers $i, j$ where $1\le i\le j \le n$ such that $\sum\limits_{k=i}^j$$a_k$ is divisible by $n$.

For example, when $n=5$, the sequence $-12, 53, 3, 3, -44$ contains a subsequence $52, 3, 3, -44$ whose sum is $15$, which is divisible by $5$.

Hint. Consider the $n$ sums of $a_1, a_1 + a_2, a_1 + a_2 + a_3, \ldots, a_1 + a_2, + \cdots + a_n$.

If any of these sums is divisible by $n$, then we are done. What happens if none of them is divisible by $n$?

  • 1
    $\begingroup$ What would happen if you tried to use induction? $\endgroup$
    – abiessu
    Mar 5, 2014 at 3:36

2 Answers 2


Consider the $n$ sums: $$s_k = \sum_{j=1}^k a_j$$

and their remainder after a division by $n$: $$n|s_k-r_k$$

There are $n$ of them. If one of them is 0: take $s_k$ and you are done.

Otherwise, there are $n-1$ possibilities for the possible values of $r_k$, so (pigeonhole principle) there are $p<q$ such as $r_p = r_q$, and so you take $\sum_{j=p+1}^q a_j$ and you are done.

  • 3
    $\begingroup$ The word you want is "remainder", not "rest". (Though the Spanish word is "resto".) $\endgroup$
    – Pedro
    Mar 5, 2014 at 4:01
  • $\begingroup$ Can you clarify what you mean by "if one of them is 0, then take $s_k$ and you are done" ? Do you mean that their is no remainder to consider? $\endgroup$
    – E 4 6
    Mar 5, 2014 at 4:05
  • $\begingroup$ @user3358732: is for example $r_2=0$, then $a_1 + a_2$ is a multiple of $n$. $\endgroup$
    – mookid
    Mar 5, 2014 at 4:06

Since we are interested in divisibility, we can consider the problem mod n. So our sequence $a_1,a_2,\ldots,a_n$ are all in $\{0,1,2,...,n-1\}$. Assume that there is no sequence of length 1 that adds to a multiple of $n$. Then use induction. Obviously for $n=1$ this is true. Try using induction.


You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .