Given an array $A$ and an index $c$, prove there always exists a subarray whose sum $\pmod {i} = 0$
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.