---
tag: J00Z252GRE
kind: statement
role: theorem
name: Erdős–Ginzburg–Ziv theorem
msc: [11B30, 11P70, 05D99]
uses: [03VFZ2WETT]
about: [3NM362A2JG]
sources:
  - url: https://en.wikipedia.org/wiki/Zero-sum_problem
---

## Statement

Let $n$ be a positive integer.
Then among any $2n - 1$ integers, not necessarily distinct, there are $n$ whose sum is divisible by $n$.

## Remarks

The proof first treats a prime $n = p$, using the Chevalley–Warning theorem or the [[Cauchy–Davenport theorem|F7K7XFACSG]].
For composite $n = ab$, the cases $a$ and $b$ imply the case $n$.
One repeatedly extracts $2b - 1$ disjoint groups of $a$ elements, each with sum divisible by $a$.
Then one applies the case $b$ to the $2b - 1$ group sums divided by $a$.
The number $2n - 1$ cannot be lowered.
The $2n - 2$ integers consisting of $n - 1$ zeros and $n - 1$ ones have no $n$ elements with sum divisible by $n$.
Indeed, any $n$ of them contain $j$ ones with $1 \le j \le n - 1$, so their sum $j$ is not a multiple of $n$.
For $n = 2$: among any three integers, two have the same parity, so their sum is even.

## Explanations

### L1 human

Write down $2n - 1$ whole numbers.
You can always choose exactly $n$ of them whose sum is a multiple of $n$.
For example, among any $5$ integers, some $3$ add up to a multiple of $3$.

### L2 human

The theorem is the starting point of zero-sum theory in [[additive combinatorics|3NM362A2JG]].
In the language of the [[integers modulo $n$|03VFZ2WETT]], every sequence of $2n - 1$ elements of $\Z/n\Z$ has a subsequence of length $n$ with sum $0$.
Related invariants, such as the Davenport constant, ask for the shortest length that forces a nonempty zero-sum subsequence.