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.


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.

| cite | improve this answer | |
  • $\begingroup$ A ha! So two of these sums will have the same remainder, so their difference is divisible by p, right? $\endgroup$ – user1526710 Sep 30 '12 at 17:38
  • $\begingroup$ @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. $\endgroup$ – Ross Millikan Sep 30 '12 at 17:47

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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