Given an array $A$ and an index $i$, prove there always exists a subarray whose sum $\pmod {i} = 0$.

Question

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

I get stuck halfway through the inductive step. Here is my work:

Let $p(n)$ denote the statement we're proving.

Base case: For $n = 1$ the statement holds (every positive integer mod $1 = 0$), so the subarray $S$ is the array $A$ itself.

Induction assumption: Suppose $p(n)$ is true.

Inductive step: For an array of size $n+1$ we consider the following two cases:

Case (1): $i \in \{1, 2, ..., n\}$. It follows directly from the inductive assumption that $p(n+1)$ is true (since $i \neq n+1$).

Case (2): $i = n+1$ (...).

This is where I get stuck, how would you argue that $S$ exists here?

Answer 1

All you have left is case $(2)$. This case cannot (as far as I can tell) be solved inductively, but it can be solved with the pigeonhole principle. I will give you a hint as to how this can be done.

The sum of a contiguous sub-array can be written as the difference of two prefix sums, e.g, $$ a_3+a_4+a_5=(a_1+a_2+a_3+a_4+a_5)-(a_1+a_2) $$ Furthermore, the contiguous sum is equivalent $\pmod {n+1}$ to zero if and only if the two prefix sums are equivalent to each other $\pmod {n+1}$. So you just need to show there exist two equal prefix sums. The pigeonhole principle naturally applies to showing there exist two equal things...