From Wikipedia, the free encyclopedia
A Cauchy–Davenport-lemma az additív számelmélet egyik fontos elemi tétele.
Ha prímszám, és szerinti maradékosztályok nemüres halmazai és , akkor
Továbbá, ha akkor tartalmaz minden szerinti maradékosztályt. Itt az
komplexusösszeget jelöli.
Először a második állítást igazoljuk. Tegyük tehát fel, hogy . Legyen tetszőleges szerinti maradékosztály. Legyen . Nyilván és elemszáma ugyanannyi (hiszen elemeit tükröztük -re és ciklikusan elforgattuk -vel). Mivel így az és halmazoknak van közös elemük. De ha ilyen elem, akkor , azaz kongruens egy -beli és egy -beli elem összegével.
A tétel első, lényegesebb állítását elemszámára vonatkozó teljes indukcióval igazoljuk. Ha egyetlen elemből, mondjuk -ből áll, akkor a halmazok összege , tehát -nak -vel való ciklikus körbetoltja, ennek valóban annyi eleme van, mint -nak.
Tegyük most fel, hogy .
Lemma. Van olyan maradékosztály hogy ha , akkor nemüres és nem egyenlő -vel.
Bizonyítás. Válasszuk -ből a különböző elemeket. Van olyan , amire , mert különben zárt lenne a hozzárendelésre, de ekkor bármelyik eleméből kiindulva ismételt hozzáadással lépésben megkapnánk minden maradékosztályt, tehát elemszáma lenne, ellentmondás. Létezik tehát az említett elem. Azt állítjuk, hogy a választás jó. Valóban, nemüres, mert tartalmazza a elemet. Ugyanakkor , hiszen, ha lenne , amire teljesülne, akkor lenne, amit kizártunk.
A tétel bizonyításához visszatérve jegyezzük meg, hogy és hiszen mindkét esetben ciklikus eltoltról van szó. Elég tehát -et igazolni.
Legyen , . Ezek nemüres halmazok és a szita formula szerint . Könnyű látni, hogy és mivel , az indukciós hipotézis szerint . Ezzel viszont készen vagyunk, hiszen az eddigiek szerint
A fenti egyenlőtlenség felhasználható az Erdős–Ginzburg–Ziv-tétel bizonyításánál.
Seamless Wikipedia browsing. On steroids.
Every time you click a link to Wikipedia, Wiktionary or Wikiquote in your browser's search results, it will show the modern Wikiwand interface.
Wikiwand extension is a five stars, simple, with minimum permission required to keep your browsing private, safe and transparent.