Given an array $A$ and an index $c$, prove there always exists a subarray whose sum $\pmod {i} = 0$ Given an array $A$ of positive integers with size $m$ and an array index $c$ (indexing starts at $1$). Prove using mathematical induction over $m$ that there always exists a contiguous subarray $S$ in $A$ such that the (sum of the elements of $S$) $\pmod {i} = 0.$


I'm unable to find the correct approach to solve this. I'm sure the Pigeonhole Principle will be useful here, but I don't know how to correctly apply it within the proof. Can someone point me in the right direction?
Let's try to do it, no induction involved.

Suppose you augment your initial list $A = [a_1, a_2, ..., a_m]$ with a new element at the beginning $a_0 = 0$, $A' = [a_0, a_1, ..., a_m]$. 

Now build partial sums of $A'$, such that $P_i = \sum_0^i a_j$. Notice that the sums of elements in the initial list from positions $b$ to position $e$ is $\sum_b^e a_i = P_e - P_{b - 1}$. Notice $P_0 = 0$ is defined since we added $a_0$. This is a very common trick when you care about the sums of intervals.

Back to the problem, you need to proof there exist two index $i &lt; j$ such that $c | (P_j - P_i)$. This is equivalent to say that there exist two index $i &lt; j$ such that $P_i \equiv P_j \mod c$. We only care about remainder of each element in $P$ if they are divided by $c$, and moreover we should only show that at least two elements have the same remainder.

Now notice the number of different remainders given $c$ is at most $c$ and the length of the list $P$ is $|P| = m + 1$. Since $c \le m &lt; |P|$ by the Pigeonhole principle you can guarantee at least two elements in $P$ have the same remainder.