Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

Given a sequence of $p$ integers $a_1, a_2, \ldots, a_p$, show that there exist consecutive terms in the sequence whose sum is divisible by $p$. That is, show that there are $i$ and $j$, with $1 \leq i \leq j \leq p$, such that $a_i + a_{i+1} + \cdots + a_j$ is divisible by $p$.

I'm having trouble with labeling which entities are the pigeons, and which are the pigeonholes. I think somewhere down the line, there has to be more different sums than $p$, but that is just a guess.

share|cite|improve this question
You may find of interest a similar Pigeonhole argument: if $\rm\:n\:$ is coprime to $10\,$ then every integer with at least $\rm\:n\:$ digits $\ne 0$ has a contiguous digit subsequence that forms an integer $\ne 0$ divisible by $\rm\:n.\ \ $ – Bill Dubuque Sep 30 '12 at 18:29
up vote 3 down vote accepted

Hint: The holes are remainders on division by $p$. Consider $\sum_{i=1}^k a_i$ for $k=1,2,3 \ldots,p$ If any are divisible by $p$ you are done. If not, You have $p$ sums with only $p-1$ values of remainder allowed.

share|cite|improve this answer
A ha! So two of these sums will have the same remainder, so their difference is divisible by p, right? – user1526710 Sep 30 '12 at 17:38
@user1526710: Exactly. Then if the two that match are $k_1$ and $k_2$, the sum from $k1+1 through $k_2$ is the one you want. – Ross Millikan Sep 30 '12 at 17:47

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.