proof of Cauchy-Davenport theorem

There is a proof, essentially from here http://www.math.tau.ac.il/ nogaa/PDFS/annr3.pdf(Imre Ruzsa et al.):

Let $|A|=k$ and $|B|=l$ and $|A+B|=n$. If $n\ge k+l-1$, the assertion is true, now assume . Form the polynomial $f(x,y)={\prod }_{c\in A+B}(x+y-c)={\sum }_{i+j\le n}{f}_{ij}*x^i*y^j$. The sum is over $i$,$j$ with $i+j\le n$, because there are $n$ factors in the product.

Since $Z_p$ is a field, there are polynomials $g_i$ of degree and $h_j$ of degree such that $g_i(x)=x^i$ for all $x\in A$ and $h_j(y)=y^j$ for all $y\in B$. Define a polynomial $p$ by .

This polynomial coincides with $f(x,y)$ for all $x$ in $A$ and $y$ in $B$, for these $x$,$y$ we have, however, $f(x,y)=0$. The polynomial $p(x,y)$ is of degree in $x$ and of degree in $y$. Let $x\in A$, then $p(x,y)=\sum p_j(x)*y^j$ is zero for all $y\in B$, and all coefficients must be zero. Finally, $p_j(x)$ is zero for all $x\in A$, and all coefficients $p_{ij}$ of $p(x,y)=\sum p_{ij}*x^i*y^j$ must be zero as elements of $Z_p$.

Should the assertion of the theorem be false, then there are numbers $u$,$v$ with and and .

But the monomial $x^u*y^v$ does not appear in the second and third sum, because for $j=v$ we have , and for $i=u$ we have . Then $p_{uv}=0$ is $modulop$ equal to $f_{uv}$, this is equal to the binomial coefficient $\left(\genfrac{}{}{0pt}{}{n}{v}\right)$, which is not divisible by $p$ for , a contradiction. The Cauchy-Davenport theorem is proved.

Title	proof of Cauchy-Davenport theorem
Canonical name	ProofOfCauchyDavenportTheorem
Date of creation	2013-03-22 14:34:49
Last modified on	2013-03-22 14:34:49
Owner	Wolfgang (5320)
Last modified by	Wolfgang (5320)
Numerical id	26
Author	Wolfgang (5320)
Entry type	Proof
Classification	msc 11B05