Az állítást $k$ szerinti teljes indukcióval bizonyítjuk.
Ha $k=1$, akkor kétféle összeg van: $0$ és $a_1$, ezért az állítás igaz, sőt a kívánt $1$ helyett kétféle maradékot adtunk $p$-vel osztva.
Tegyük fel, hogy at állítás igaz $k=k_0$-ra, ahol $2\le k_0<p$. Jelölje az $e_1{a}_1+\text{...}+e_{k_0}{a}_{k_0}$-tagú összegeket $s_1\mathrm{,}{s}_2\mathrm{,}\text{...}\mathrm{,}{s}_n$. Az indukciós feltevés szerint ezek legalább $k_0$-féle maradékot adnak $p$-vel osztva. Tekintsük most a $\left(k_0+1\right)$ tagú összegeket, és csoportosítsuk őket $e_{k_0+1}$ értéke szerint. Ha $e_{k_0}=0$, akkor éppen az $s_1\mathrm{,}{s}_2\mathrm{,}\text{...}\mathrm{,}{s}_n$ összegeket kapjuk; amikor $e_{k_0+1}=1$, akkor pedig az $s_1+a_{k_0+1}\mathrm{,}{s}_2+a_{k_0+1}\mathrm{,}\text{...}\mathrm{,}{s}_n+a_{k_0+1}$ számokat.
Ha $s_1\mathrm{,}{s}_2\mathrm{,}\text{...}\mathrm{,}{s}_n$ teljes maradékrendszer modulo $p$ (azaz $p$-vel osztva minden maradékot kiadnak), akkor készen vagyunk, hiszen a különböző maradékok száma $p\ge k$.
Feltehetjük tehát, hogy $s_1\mathrm{,}{s}_2\mathrm{,}\text{...}\mathrm{,}{s}_n$ nem adnak ki minden maradékot $p$-vel osztva.
Azt állítjuk, hogy ekkor $s_1+a_{k_0+1}\mathrm{,}{s}_2+a_{k_0+1}\mathrm{,}\text{...}\mathrm{,}{s}_n+a_{k_0+1}$ valamelyike olyan maradékot ad $p$-vel osztva, amely $s_1\mathrm{,}\text{...}\mathrm{,}{s}_n$ maradékai között nem szerepel. Ebből az állítás már következik, mivel így a $\left(k_0+1\right)$-tagú összegek legalább $1$-gyel több féle maradékot adnak $p$-vel osztva, mint a $k_0$-tagúak.
Tekintsük a $\mathrm{0,}{a}_{k_0+1}\mathrm{,2}{a}_{k_0+1}\mathrm{,}\text{...}\mathrm{,}\left(p-1\right)a_{k_0+1}$ számokat. Mivel $a_{k_0+1}$ nem osztható $p$-vel, azért ezek $p$-vel osztva mind különböző maradékot adnak (ha $i{a}_{k_0+1}$ és $j{a}_{k_0+1}$ ugyanazt a maradékot adja, akkor különbségük, $\left(i-j\right)a_{k_0+1}$ osztható $p$-vel, ami csak $i=j$ esetén lehetséges); így ez egy teljes maradékrendszer modulo $p$.
Ezen számok között biztosan szerepel olyan, amelynek $p$-vel való osztási maradéka az $s_i$-k maradékai között nem szerepel, hiszen feltételezésünk szerint az $s_i$-k nem adnak ki minden lehetséges maradékot. Legyen az első ilyen szám az $l\cdot a_{k_0+1}$. Mivel a $0$ szerepel az $s_i$-k között, $l$ nem lehet $0$, azaz $l\ge 1$.
A feltevés szerint $\left(l-1\right)a_{k_0+1}$ maradéka előfordul az $s_i$-k maradékai között, mondjuk