قبل از هر چیز باید $A$ و $B$ تهی نباشند.اگر $A= \emptyset $ و $B=Z_p$ آنگاه هیچ کدام از حکم های فوق درست نیستند.(در واقع این مطلب به $Cauchy-Davenport-Theorem$ مشهور است.)
برای اثبات به یک لم نیاز است.
لم:اگر $A$ و $B$ دو زیر مجموعه دلخواه غیر تهی و متناهی از $Z$ باشند آنگاه $|A+B| \geq |A|+|B|-1$.
اثبات:اگر $A+x$ انتقال $A$ تحت عدد صحیح $x$ باشد با توجه به اینکه تابع
$ \phi :A \longrightarrow A+x, \forall a \in A: \phi (a)=a+x$
خوش
تعریف یک به یک و پوشاست،پس $|A+x|=|A|$ لذا می توان حالتی را در نظر بگیریم که $MinA=0=MaxB$.از اینجا میشه به راحتی نتیجه گرفت که :
$A \cap B=[0]\wedge A \cup B \subseteq A+B (?)$
$\Rightarrow |A+B| \geq |A \cup B|=|A|+|B|-|A \cap B=|A|+|B|-1$
حالا برگردیم به مسأله:
اگر $|A|=1$ یا $|B|=p$ به راحتی می توان نشان داد که $|A+B| \geq |A|+|B|-1$ و حکم ثابت است.پس حالتی را در نظر می گیریم که $|A|>1$ و $0<|B|<p ( \emptyset \neq B \neq Z_p)$ بنابه استدلالی که در لم بالا آمد می توان فرض گفت که عضوی غیر صفر از $Z_p$ مانند $g$ موجود است که $0,g \in A$.حالا عدد صحیح $n$ را طوری انتخاب کنید که $ng \in B, \neg ((n+1)g \in B)$.حالا به جای $B$ انتقال $B-ng$ را از آن را در نظر بگیرید تا بتوان فرض کرد که $0 \in B, \neg (g \in B)$.با این استدلالات داریم:
$A \cap B \neq \emptyset $ و $A \cup B \neq \emptyset $ و $ \neg (g \in A \cup B)$ و$A \cap B+A \cup B \subseteq A+B$
$ \Rightarrow |A+B| \geq |A \cap B+A \cup B| \geq Min[p , |A \cap B|+|A \cup B|-1]=Min[p,|A|+|B|-1]$
حالا اگر $Min[p,|A|+|B|-1]=|A|+|B|+1$ آنگاه حکم ثابت است.در غیر این صورت:
$Min[p,|A|+|B|-1]=p \Rightarrow |A+B| \geq p \Rightarrow |A+B|=p \Rightarrow A+B=Z_p$
$ \Box $
در این اثبات از نماد $[ ]$ برای مجموعه استفاده شده است.
