Difference between revisions of "Cauchy-davenport"
m |
|||
| Line 1: | Line 1: | ||
| − | The Cauchy-Davenport | + | The Cauchy-Davenport Theorem states that for all nonempty sets <math>A,B \subseteq \mathbb{Z}/p\mathbb{Z}</math> , we have that |
<cmath>|A+B| \geq \min\{|A|+|B|-1,p\},</cmath> | <cmath>|A+B| \geq \min\{|A|+|B|-1,p\},</cmath> | ||
where <math>A+B</math> is defined as the set of all <math>c \in \mathbb{Z}/p\mathbb{Z}</math> that can be expressed as <math>a+b</math> for <math>a \in A</math> and <math>b \in B</math>. | where <math>A+B</math> is defined as the set of all <math>c \in \mathbb{Z}/p\mathbb{Z}</math> that can be expressed as <math>a+b</math> for <math>a \in A</math> and <math>b \in B</math>. | ||
| + | |||
| + | == Proof of the Cauchy-Davenport Theorem by the Combinatorial Nullstellensatz == | ||
| + | |||
| + | == Proof by Induction == | ||
| + | |||
| + | == Applications of the Cauchy-Davenport Theorem == | ||
Latest revision as of 13:39, 20 September 2019
The Cauchy-Davenport Theorem states that for all nonempty sets 
, we have that
![\[|A+B| \geq \min\{|A|+|B|-1,p\},\]](http://latex.artofproblemsolving.com/0/9/f/09f3124f98a7f614911df0ae09fe454a96e533b2.png)
where 
is defined as the set of all 
that can be expressed as 
for 
and 
.
