[proofplan] We induct on $n$. The base case is the prime case $n = p$, proved by partitioning the $2p - 1$ sorted elements into $p - 1$ pairs and one singleton, then applying the [Iterated Cauchy-Davenport](/theorems/2605) theorem to show the iterated sum set covers all of $\mathbb{Z}_p$, so in particular $0$ is representable. The general case $n = pm$ ($p$ prime, $m > 1$) uses the induction hypothesis for $m$ to extract $2p - 1$ disjoint $m$-element blocks whose sums are divisible by $m$, reduces modulo $p$, and applies the prime case to select $p$ of these blocks whose combined $pm = n$ elements sum to $0$ modulo $n$. [/proofplan] [step:Prime case setup: sort the sequence and split into two sub-cases] Let $n = p$ be prime. We are given $2p - 1$ elements $a_1, \ldots, a_{2p-1} \in \mathbb{Z}_p$. After reindexing, assume they are sorted: \begin{align*} 0 \leq a_1 \leq a_2 \leq \cdots \leq a_{2p-1} < p. \end{align*} We distinguish two cases based on whether any value appears at least $p$ times. [/step] [step:Prime case 1: if some value appears $p$ times, extract a $p$-element zero-sum subset directly] If there exist $p$ equal terms among $a_1, \ldots, a_{2p-1}$, say $a_i = a_{i+1} = \cdots = a_{i+p-1} = c$ for some $c \in \mathbb{Z}_p$ and some index $i$, then the subset $I = \{i, i+1, \ldots, i+p-1\}$ has $|I| = p$ and \begin{align*} \sum_{j \in I} a_j = p \cdot c \equiv 0 \pmod{p}, \end{align*} since $p \cdot c = 0$ in $\mathbb{Z}_p$. This gives the required $p$-element zero-sum subset. [guided] This case is straightforward: if any residue class appears at least $p$ times, we select exactly $p$ copies. Their sum is $p$ times that residue, which vanishes modulo $p$ because $p \equiv 0$ in $\mathbb{Z}_p$. Why is $p$ copies the right number? We need a subset of size exactly $p$. If some value appears $p$ or more times, choosing $p$ copies of it gives a subset of the correct size whose sum is a multiple of $p$. If no value appears $p$ or more times, we are in the second case, where no single value dominates and we need a more sophisticated argument. [/guided] [/step] [step:Prime case 2: form two-element sets and a singleton, then apply iterated Cauchy-Davenport] Assume no value appears $p$ or more times. Since the sequence is sorted and has $2p - 1$ terms, define the sets \begin{align*} A_i &= \{a_i, \, a_{i+p-1}\} \quad \text{for } i = 1, 2, \ldots, p-1, \\ A_p &= \{a_{2p-1}\}. \end{align*} Each $A_i$ for $i \leq p - 1$ draws one element from the "first half" ($a_1, \ldots, a_{p-1}$) and one from the "second half" ($a_p, \ldots, a_{2p-2}$) of the sorted sequence (with indices offset by $p - 1$). Since no value appears $p$ times, the elements $a_i$ and $a_{i+p-1}$ cannot all be equal for any run of $p$ consecutive terms, so in particular $a_i \neq a_{i+p-1}$ for each $i = 1, \ldots, p-1$. Therefore $|A_i| = 2$ for $i = 1, \ldots, p-1$, and $|A_p| = 1$. We verify the size condition for the [Iterated Cauchy-Davenport](/theorems/2605) theorem with $k = p$ sets in $\mathbb{Z}_p$: \begin{align*} \sum_{i=1}^{p} |A_i| = 2(p - 1) + 1 = 2p - 1 \leq p + p - 1 = 2p - 1. \end{align*} The condition $\sum |A_i| \leq p + k - 1 = 2p - 1$ holds with equality. By the [Iterated Cauchy-Davenport](/theorems/2605) theorem: \begin{align*} |A_1 + A_2 + \cdots + A_p| \geq \sum_{i=1}^{p} |A_i| - p + 1 = (2p - 1) - p + 1 = p. \end{align*} Since $A_1 + \cdots + A_p \subseteq \mathbb{Z}_p$ and $|\mathbb{Z}_p| = p$, we conclude $A_1 + A_2 + \cdots + A_p = \mathbb{Z}_p$. In particular, $0 \in A_1 + A_2 + \cdots + A_p$. This means there exist choices $s_i \in A_i$ for each $i = 1, \ldots, p$ such that $s_1 + s_2 + \cdots + s_p = 0$ in $\mathbb{Z}_p$. Each $s_i$ is one of the two elements of $A_i$ (or the single element if $i = p$), so the chosen $s_1, \ldots, s_p$ correspond to exactly $p$ terms from the original sequence $a_1, \ldots, a_{2p-1}$. These $p$ terms form the required subset $I$ with $|I| = p$ and $\sum_{i \in I} a_i \equiv 0 \pmod{p}$. [guided] The construction of the sets $A_i$ is designed to accomplish two things simultaneously: (i) cover all $2p - 1$ terms of the sequence (each term appears in exactly one $A_i$), and (ii) ensure each $A_i$ has size $2$ (except the last singleton) so that the iterated Cauchy-Davenport bound is tight enough. Why does $a_i \neq a_{i+p-1}$? By assumption, no value appears $p$ or more times. Since the sequence is sorted, if $a_i = a_{i+p-1}$, then $a_i = a_{i+1} = \cdots = a_{i+p-1}$ (all intermediate values are squeezed between two equal endpoints in a sorted list), giving $p$ consecutive equal terms. This contradicts our assumption that no value appears $p$ times. With $|A_i| = 2$ for $i = 1, \ldots, p-1$ and $|A_p| = 1$, the total size is $\sum |A_i| = 2(p-1) + 1 = 2p - 1$. The iterated Cauchy-Davenport theorem requires $\sum |A_i| \leq p + k - 1$ where $k = p$ is the number of sets, giving $2p - 1 \leq 2p - 1$, which holds with equality. The iterated theorem then gives $|A_1 + \cdots + A_p| \geq (2p - 1) - p + 1 = p$. Since $|A_1 + \cdots + A_p| \leq |\mathbb{Z}_p| = p$, the sum set equals all of $\mathbb{Z}_p$. In particular, $0$ is achievable as a sum $s_1 + \cdots + s_p$ with $s_i \in A_i$. The element $s_i$ chosen from $A_i$ selects exactly one of the two original sequence terms in that pair. Since the sets $A_1, \ldots, A_p$ partition $\{a_1, \ldots, a_{2p-1}\}$ (each index appears in exactly one $A_i$), choosing one element from each $A_i$ selects exactly $p$ terms from the original sequence. These $p$ terms sum to $0$ in $\mathbb{Z}_p$. [/guided] [/step] [step:General case: write $n = pm$ with $p$ prime and $m > 1$, and extract $2p - 1$ blocks of size $m$] For the general case, write $n = pm$ where $p$ is a prime factor of $n$ and $m = n/p > 1$. We are given $2n - 1 = 2pm - 1$ elements $a_1, \ldots, a_{2pm-1} \in \mathbb{Z}_n$, and we induct on $n$. By the induction hypothesis applied to $m$ (which is valid since $m < n$): any $2m - 1$ elements of $\mathbb{Z}_m$ contain an $m$-element subset summing to $0 \pmod{m}$. Equivalently, any $2m - 1$ elements of $\mathbb{Z}_n$ contain an $m$-element subset whose sum is divisible by $m$. We use this to extract disjoint $m$-element blocks $S_1, S_2, \ldots, S_{2p-1}$ from $\{1, \ldots, 2pm-1\}$, each satisfying $\sum_{j \in S_i} a_j \equiv 0 \pmod{m}$. **Extraction procedure.** We select the blocks one at a time. After selecting $S_1, \ldots, S_\ell$ (for $0 \leq \ell \leq 2p - 2$), the number of remaining indices is \begin{align*} (2pm - 1) - \ell m. \end{align*} For $\ell \leq 2p - 2$, this equals $(2pm - 1) - \ell m \geq (2pm - 1) - (2p - 2)m = 2m - 1$. So at least $2m - 1$ elements remain, and the induction hypothesis guarantees the existence of an $m$-element subset among them whose sum is divisible by $m$. This subset becomes $S_{\ell+1}$. Repeating this $2p - 1$ times produces disjoint sets $S_1, \ldots, S_{2p-1}$, each of size $m$, with \begin{align*} \sum_{j \in S_i} a_j = m \cdot b_i \end{align*} for some $b_i \in \mathbb{Z}$ (i.e., the sum is divisible by $m$). Define $b_i \in \mathbb{Z}_p$ as the reduction of $\frac{1}{m}\sum_{j \in S_i} a_j$ modulo $p$. [guided] The two-level strategy is: first group the $2pm - 1$ terms into $m$-element blocks that each sum to a multiple of $m$, then combine $p$ of those blocks into a sum that is also a multiple of $p$, hence a multiple of $pm = n$. Why can we always find the next block? After choosing $\ell$ blocks ($0 \leq \ell \leq 2p - 2$), the remaining count is $(2pm - 1) - \ell m$. At the worst case $\ell = 2p - 2$: \begin{align*} (2pm - 1) - (2p - 2)m = 2pm - 1 - 2pm + 2m = 2m - 1. \end{align*} So there are exactly $2m - 1$ elements left, which is exactly what the induction hypothesis for $m$ requires. For $\ell < 2p - 2$, there are strictly more than $2m - 1$ elements remaining, so the hypothesis certainly applies. After this extraction, we have $2p - 1$ values $b_1, \ldots, b_{2p-1}$, where $b_i$ represents the "quotient" $\frac{1}{m}\sum_{j \in S_i} a_j$ modulo $p$. The problem reduces to finding $p$ of these $b_i$ that sum to $0 \pmod{p}$. [/guided] [/step] [step:Apply the prime case to the block sums and conclude] We now have $2p - 1$ elements $b_1, \ldots, b_{2p-1} \in \mathbb{Z}_p$. By the prime case (proved above, since $p$ is prime), there exist $p$ indices $i_1, \ldots, i_p \in \{1, \ldots, 2p-1\}$ such that \begin{align*} b_{i_1} + b_{i_2} + \cdots + b_{i_p} \equiv 0 \pmod{p}. \end{align*} Define $I = S_{i_1} \cup S_{i_2} \cup \cdots \cup S_{i_p}$. Since the blocks $S_{i_1}, \ldots, S_{i_p}$ are pairwise disjoint and each has $|S_{i_k}| = m$, the set $I$ has $|I| = pm = n$ elements from the original sequence. The sum of the original sequence over $I$ is \begin{align*} \sum_{j \in I} a_j = \sum_{k=1}^{p} \sum_{j \in S_{i_k}} a_j = \sum_{k=1}^{p} m \cdot b_{i_k} = m \cdot \left(\sum_{k=1}^{p} b_{i_k}\right). \end{align*} Since $\sum_{k=1}^{p} b_{i_k} \equiv 0 \pmod{p}$, we have $\sum_{k=1}^{p} b_{i_k} = p \cdot q$ for some integer $q$. Therefore \begin{align*} \sum_{j \in I} a_j = m \cdot p \cdot q = n \cdot q \equiv 0 \pmod{n}. \end{align*} The subset $I \subseteq \{1, \ldots, 2n-1\}$ has $|I| = n$ and $\sum_{j \in I} a_j \equiv 0 \pmod{n}$, completing the proof. [guided] The final step combines the two levels of the induction. Each block $S_{i_k}$ contributes a sum $m \cdot b_{i_k}$ to the total. The prime case selects $p$ blocks whose $b$-values sum to $0 \pmod{p}$, so the total sum is $m \cdot (p \cdot q) = n \cdot q$ for some integer $q$, which vanishes modulo $n$. Why does the bookkeeping with $2pm - 1$ terms work out? We need to extract $2p - 1$ blocks of size $m$ (using $(2p-1)m$ indices) from a sequence of $2pm - 1$ terms. Since $(2p-1)m = 2pm - m < 2pm - 1$ (as $m \geq 2$), we have more than enough terms. The sequential extraction works because at each step, the number of remaining terms is at least $2m - 1$, as verified in the previous step. The choice of $n = pm$ (with $p$ prime) is always possible for $n > 1$: every integer $n > 1$ has a prime factor $p$, and $m = n/p < n$ ensures the induction can proceed. The base case of the induction is $n = 1$, which is vacuous (any single element sums to $0 \pmod{1}$). [/guided] [/step]