Consecutive Integer Sum of an m-member Sequence is Divisible by m Proof

86 Views Asked by At

This problem is found in Richard A. Brauldi's book on Introductory Combinatorics. It goes as follows:

Given m integers $a_1, a_2, ... ,a_m$, there exist integers $k$ and $l$ with $0 \le k \lt l \le m$ such that $a_{k+1} + a_{k+2} + ... + a_l$ is divisible by $m$. Less formally, there exist consecutive $a$'s in the sequence $a_1, a_2, . .. ,a_m$ whose sum is divisible by $m$.

The author starts the proof like this:

Consider the $m$ sums:

$a_1, a_1 + a_2, a_1 + a_2 + a_3, ..., a_1 + a_2 + a_3 + ... + a_m$

If any of these sums are divisible by $m$, then the conclusion holds. Thus, we may suppose that each of these sums has a nonzero remainder when divided by $m$ and so ...

The author then continues with the proof; yet, I haven't understood how it is that we can just suppose that the sums have a nonzero remainder? I at first thought the author was attempting at a proof by contradiction, but the author continues to demonstrate how it is possible to construct with integers $k$ and $l$ the sequence $a_{k + 1}, ..., a_l$, the sum of the terms of which is divisible by $m$. But this doesn't contradict the supposition we've took previously, because we've only considered series beggining with the first term, $a_1$ and not any general sequence. Could anyone elucidate the flaw in my reasoning? That you in advance.

1

There are 1 best solutions below

1
On

If any of these sums are divisible by $m$, then the conclusion holds.

Because of this, it suffices to prove that the conclusion holds when none of those sums is divisible by $m$, i.e. the remainders are nonzero.