Főmenü megnyitása

Cauchy–Davenport-lemma

(Cauchy-Davenport-lemma szócikkből átirányítva)

A Cauchy–Davenport-lemma az additív számelmélet egyik fontos elemi tétele.

A tétel állításaSzerkesztés

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.

A tétel bizonyításaSzerkesztés

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

 

Lásd mégSzerkesztés

A fenti egyenlőtlenség felhasználható az Erdős–Ginzburg–Ziv-tétel bizonyításánál.

SzakirodalomSzerkesztés

  1. A. L. Cauchy: Recherches sur les nombers, J. Ecole Polytechniques, 9(1813), 99–123.
  2. H. Davenport: On the addition of residue classes, J. London Math. Soc., 10(1935), 30–32.
  3. H. Davenport: A historical note. J. London Math. Soc., 22 (1947), 100–101.

További információkSzerkesztés