Cauchy-Davenport Theorem

The well known result $|A+B| \ge |A|+|B|-1$ in the reals is also true modulo $p$ (at least when $p$ is prime), and it is called the Cauchy Davenport theorem. Of course, this is not quite true - $|A+B|>p$ is impossible, and when $|A|+|B|-1>p$ then $|A+B|=p$. So we can write $|A+B| \ge |A|+|B|-1$.

There are several proofs of the Cauchy Davenport theorem. One utilizes the amazing combinatorial nullstellensatz of Noga Alon.

The simplest, presented by Razvan Gelca at several MOPs, involves the ingenious use of the Dyson move. Assume $|A|+|B| \le p+1$, because else just throw out elements from $B$ until we obtain this state as this cannot increase $|A+B|$. Consider the following two transformations:

1. Take constants $c_1$ and $c_2$ (possibly $0$) and change $A$ into $A+c_1$ (the set of $a+c_1$ for $a$ in $A$) while $B$ becomes $B+c_2$ (the set of $b+c_1$ for $b$ in $B$). This is a translation.

2. Replace the two sets $A$ and $B$ by the union of $A$ and $B$, $C$, and the intersection of $A$ and $B$, $D$, as long as $D$ is nonempty. Then rename $C$ and $D$ as $A$ and $B$ in some order.

These above two steps do not increase the size of $|A+B|$ and also do not change $|A|+|B|-1$, and also do not make any set empty. This is clearly true for step $1$, and for step $2$ it suffices to note that if we have $x+y$ for $x$ in $A$ intersect $B$ and $y$ in the union, then WLOG $y$ is in $B$. Since $x$ is in $A$, $x+y$ is in $A+B$.

Note that applying transformation $2$ strictly increases $max(|A|,|B|)-min(|A|,|B|)$ even while $|A|+|B|-1$ is fixed, so at some point it will become impossible to apply transformation $2$ even after many translations. At this point WLOG $|A| \ge |B|$.

Case 1: $|B|>1$. Then apply transformation $1$ to WLOG that $B$ has $0$ and some nonzero $k$ (and fix $A$). Now, for any $A$ in $a$, translate $B$ to $B+a$ while fixing $A$. The element $k$ maps to $a+k$ which must be an element of $A$, else we could successfully apply operation $2$. So $a$ in $A$ implies $a+k$ in $A$ for some $k$ nonzero mod $p$. Then take an element $x$ of $A$ and then $x$, $x+k$,... $x+(p-1)k$ are all in $A$. But this represents a complete residue system mod $p$ (because $p$ is prime), so $A$ has all elements mod $p$. But then $|A+B|=p \ge |A|+|B|-1$ so we're done.

Case 2: $|B|=1$. Since $|A|+|B|-1=r$ originally for some $R$, this is still true and $|A|=R+1-|B|=r$. Then translate $B$ to have $0$ and we can write $A={a_1, a_2, ... a_r}$. So $A+B$ will be exactly $A$ and will have $r$ elements.

In all cases, we're done and the theorem is proved.

(2007 ISL N3) Let $X$ be a set of 10,000 integers, none of them is divisible by 47. Prove that there exists a 2007-element subset $Y$ of $X$ such that $a -b + c - d + e$ is not divisible by 47 for any $a,b,c,d,e \in Y.$

Let $p$ be a prime and $d$ be a factor of $p-1$. Prove that for every integer $n$, there exist integers $a_1,a_2,...,a_d$ such that $$a_1^d+a_2^d+...+a_d^d\equiv n \mod p.$$

Consider set $A= \{ a^d \bmod p \}$.

Source: AoPS

(Erdos-Ginsburg-Ziv, or EGZ) Prove that among any $2n-1$ integers, where $n$ is a positive integer, there exist $n$ who sum to a multiple of $n$.

(2013 TSTST 5) Let $p$ be a prime. Prove that any complete graph with $1000p$ vertices, whose edges are labelled with integers, has a cycle whose sum of labels is divisible by $p$.