Kvadratikus reciprocitás tétele

A kvadratikus reciprocitás tétele a matematika számelmélet nevű ágának egy nevezetes tétele; miszerint

Tételezzük fel, hogy p és q különböző páratlan prímek. Ha legalább az egyikük az 1 maradékot adja 4-gyel osztva, akkor az

kongruenciák egyszerre megoldhatóak vagy megoldhatatlanok (az x és y megoldások nem szükségképp azonosak); továbbá, ha mindkét prím a 3 maradékot adja 4-gyel osztva, akkor viszont a fenti kongruenciáknak pontosan egyike oldható meg.

A tétel a moduláris számelmélet egyik alapvető, a másodfokú kongruenciákat megoldások szempontjából jellemző tétele, és alapja az ilyeneket megtaláló eljárásoknak. Tömörebb megfogalmazása a Legendre-szimbólumok segítségével lehetséges.

Először Euler fogalmazta meg 1744-ben, majd Legendre 1785-ben bizonyítást is adott, ami azonban számos ponton hiányos, sőt rossz volt. Ezekről a kutatásokról nem tudva, 1795 májusában Gauss is felfedezte, és egyéves megfeszített munka után bizonyítania is sikerült, 1796. április 8-án. E bizonyítást a Disquisitiones Arithmeticae c. művében publikálta. A tételt egyébként ő Arany Tételnek (Theorema Aurea) nevezte, mert élete egyik legfontosabb felfedezésének tartotta.

A tétel másféle megfogalmazásai

Kvadratikus maradékok 

Ha érvényes

valamely x egész számra, akkor az a egész számot kvadratikus maradéknak nevezzük a b számra nézve, ellenkező esetben kvadratikus nem-maradéknak. Ezzel a megfogalmazással a kvadratikus reciprocitás tétele így hangzik:

 Ha p, q különböző páratlan prímek, akkor 
 amennyiben valamelyik prím 1 maradékot ad 4-gyel való maradékos osztáskor, úgy vagy mindketten kvadratikus maradékok egymásra nézve, vagy mindketten kvadratikus nem-maradékok a másikra nézve (de nem lehetséges, hogy az egyik a másikra nézve kvadratikus maradék legyen, míg a másik az egyikre kvadratikus nem-maradék);
 ellenben ha mindkét prím 3 maradékot ad 4-gyel osztva, akkor az, hogy az egyik kvadratikus maradék a másikra nézve, kizárja azt, hogy a másik is kvadratikus maradék legyen az egyikre.

Megfogalmazása a Legendre-szimbólummal 

Alkalmazva az ún. Legendre-szimbólumot a kvadratikus reciprocitás tétele azt állítja, hogy:

Ha p és q páratlan prímszámok, akkor
   

Ellenőrizhető, hogy a tétel két eddigi megfogalmazása valóban ugyanazt mondja, ugyanis ha p,q valamelyike 1-gyel kongruens (mondjuk p = 4u+1, azaz p-1 = 4u), a jobb oldal kitevője páros (felhasználva, hogy a prímek páratlanok, azaz q = 2v+1 alakú, ), így a jobb oldal értéke 1, tehát vagy mindkét bal oldali Legendre-szimbólum pozitív, vagy mindkettő negatív, azaz egyszerre kvadratikus maradékok vagy kvadratikus nem-maradékok a prímek egymásra nézve. Ha viszont mindkét prím 3-at ad néggyel osztva, akkor p = 4u+3 és q = 4v+3, azaz a jobb oldali kitevő () páratlan, így a jobb oldal értéke -1, és így a bal oldali Legendre-szimbólumok értéke különböző: ha az egyik 1, a másik -1, emiatt ha az egyik prím a másikra nézve kvadratikus maradék, akkor a másik az egyikre nézve kvadratikus nem-maradék.

Bizonyítások

Elemi bizonyítás 

Az alábbi, S.Y. Kimtől származó bizonyítás két segédtételen alapul, nevezetesen:
 segédtétel. A mod(pq) redukált maradékrendszer pq felének egészrészénél kisebb elemeinek szorzata akkor és csak akkor 1 abszolút értékű, ha p és q is egyaránt 1 maradékot adnak 4-gyel osztva;
 segédtétel A fenti szorzat p-vel osztva akkor és csak akkor ad 1 maradékot , ha q 4k+1 alakú páratlan prím, mely kvadratikus maradék p-re nézve (egyébként pedig -1 maradékot ad), hasonlóan ugyanez a szorzat akkor és csak akkor ad 1 maradékot q-val osztva, ha p 4k+1 alakú páratlan prím, mely q-ra nézve kvadratikus maradék.

Tekintsük tehát a pq szám felének (alsó) egészrészénél kisebb standard (0 … pq közti értékekkel reprezentált) redukált maradékrendszert; legyen ez Φ és legyen az e halmazba eső számok mod(pq) szorzata F! Matematikai formulákkal:
  és     .

1. segédtétel 

Ez tehát azt állítja, hogy:
  

E segédtétel bizonyítása úgy megy, hogy ügyesen párosítva szorozzuk össze Φ elemeit. A redukált maradékrendszerek elemei pontosan a multiplikatíve invertálható elemek, érthetőbben mondva, minden x∈Φ elemhez létezik olyan x*∈{0,1,2,…,pq-1} = R elem, hogy xx* ≡ 1 (mod pq). De x* nem feltétlenül eleme Φ-nek. Legyen x' = x*, ha x*∈Φ és x' = (-x)*, ha x*∉Φ, ahol (-x) azt az R-beli elemet jelöli, melyre x+(-x) = pq, azaz a pq-x∈R elemet. Könnyen belátható, hogy bármely y∈R reprezentánsra vagy y eleme Φ-nek, vagy (-y). Hiszen (-y) = pq-y teljesül, és ha y∈Φ azaz y ≤ (pq-1)/2, akkor -y ≥ (1-pq)/2; így pq-y ≥ pq+(1-pq)/2 = (pq+1)/2 ≥ (pq-1)/2. Tehát (-y) = pq-y ≥ (pq-1)/2. Emiatt (-y)∉Φ, hasonlóan ha (-y)∈Φ akkor az előzőek szerint y = (-(-y))∉Φ. Ennélfogva minden x∈Φ elemhez egyértelműen létezik olyan x' elem, mégpedig az előbbi módon definiált, hogy xx' ≡ ±1 (mod pq).

Most kiszámoljuk F-et. Párosítsuk a Φ-beli elemeket úgy, hogy x párja x', legyen, azaz ezek szorzata ±1 legyen. De lehetnek olyan elemek, melyek önmaguk párjai, legyen ezek halmaza Ψ és ezek szorzata G := ΠΨ míg Ψ halmaz Φ-re vonatkozó komplementerhalmaza legyen Ψ' := Φ\Ψ, ezek tehát nem önmaguk párjai, és így van Ψ'-beli párjuk, ezért ΠΨ' = ±1. A következő érvényes:

 F = ΠΦ = ΠΨ · ΠΨ' = ΠΨ·±1 = G·(±1) = ±G. 

Elegendő tehát G-t kiszámolni. Esetszétválasztással bizonyítható, hogy ha p,q egyaránt 1-gyel kongruensek mod(4), akkor G ≡ ±1 mod(pq), ellenben viszont nem ennyi. Ezért ez az ezzel asszociált (abszolútértékben megegyező) F-re is igaz.
 Valóban,  legyen p ≡ q ≡ 1 (4) . Ekkor Ψ elemei az u2 ≡ 1 mod(pq) és az v2 ≡ -1 mod(pq) kongruenciák azon megoldásai, melyekre u,v 0 és pq-1 fele közt van, azaz melyek Φ-be esnek. Három dolgot kell említenünk:
 Könnyen ellenőrizhető, hogy az w2 ≡ 1 mod (r) alakú kongruenciának páratlan prím r-ekre pontosan két (inkongruens) megoldása van: az 1 és az r-1 (másképp -1) osztályok (r|w2-1 = (w+1)(w-1) alapján, tekintetbe véve, hogy 0≤w<p-1).
 A w2 ≡ -1 mod(r) kongruenciáknak viszont attól függően van kettő vagy semennyi megoldásuk, hogy az r páratlan prím maradéka 4-gyel osztva mennyi. A maradék 1 vagy 3 lehet; az első esetben két megoldás van, a második esetben egy sincs (ennek bizonyítása hosszadalmas, a Wilson-tétel és a kis Fermat-tétel segítségével például bebizonyítható).
 A kínai maradéktétel szerint relatív prím m1, m2, …, mq számok m szorzata mint modulus szerinti kongruencia megoldása visszavezethető egy a tényezők mint modulusok szerinti kongruenciákból álló kongruenciarendszer megoldására. Ez a kongruenciarendszer mindig megoldható, s ha egy megoldása x0, akkor megoldása, és az eredeti kongruencia megoldása is, a teljes [x0] mod(M) maradékosztály is, ahol M :=[m1, …, mq] a modulusok legkisebb közös többszöröse. Továbbá, a mod(m) = mod(M) inkongruens megoldások száma egyenlő a fent említett kongruenciarendszer tagjainak megoldásai számainak szorzatával.
 E két állítást alkalmazva, tehát meg kell oldanunk egyrészt az u2 ≡ 1 mod(pq) kongruenciát, másrészt a v2 ≡ -1-et.
 Az előbbit a kínai maradéktétel szerint visszavezetjük egy szimultán kongruenciarendszer megoldására, nevezetesen az u2 ≡ 1 mod(p) és u2 ≡ 1 mod(q) két kongruenciából álló rendszer megoldására. A fentiek szerint mindkét kongruenciának két-két megoldása van, a szimultán kongruenciarendszer és így az eredeti, mod(pq) kongruencia inkongruens megoldásainak száma 2·2 = 4. Nyilvánvalóan ±1 egy-egy megoldása az utóbbinak, és az is, hogy ha x megoldás, akkor (-x) is az. Ezek szerint a másik két megoldás x, és (-x) alakú. Ezek közül a Φ-be esőket kell összeszorozni, tehát 1-et és x-et, vagy (-x)-et, az eredmény G1 := ±x.
 Hasonlóan járunk el az utóbbi, v2 ≡ -1 mod(pq) kongruenciával. Visszavezetve a v2 ≡ -1 (p) és v2 ≡ -1 mod(q) kongruenciákból álló rendszerre, melyeknek két-két megoldásuk van, ennek is négy mod(pq) inkongruens megoldása van. Könnyű dolgunk van, ha észrevesszük, hogy ha y ennek egy megoldása, x meg az előzőnek, akkor (xy)2 = x2y2 ≡ 1×(-1) = (-1) mod(pq). Emiatt az utóbbi minden inkongruens megoldása {±y, ±xy}. Ezek közül kettő esik Φ-be; de ellentett osztályok nem; tehát ezek szorzata G2 ±y · ±xy = ±x.
 Ennélfogva G = G1 · G2 = ±x · ±x = ± x2 = ± 1.
 Fordítva, ha  p és q közül nem mindkettő 1-gyel kongruens mod(4) , Ψ csak x2 ≡ 1 mod(pq) gyökeit tartalmazza, azaz az előzőekhez hasonlóan 1 és -1 közül az egyiket és N és -N közül az egyiket. Ezek szorzata, G = ±1 · ±N = ±N nem lesz 1-gyel kongruens mod(pq).

2. segédtétel 

A következő két állításról van szó:

A jelölések szimmetriája folytán elég az elsőt bizonyítani ezek közül. A bizonyításhoz felhasználjuk az ún. Euler-kritériumot is:
  

Legyenek

és

egyszóval D a p-vel nem osztható Φ-beli számok p-vel való osztási maradékainak szorzata! Figyelem: Δ nem halmaz, hanem rendezett elemrendszer!

F azon Φ-beli elemek szorzata, melyek nem oszthatóak sem p-vel, sem q-val; ezért ha azon Φ-beli elemek Δ halmazának elemeit szorozzuk össze, a D szorzatot kapva, melyek p-vel nem oszthatóak, de e szorzatba még azokat a Δ-belieket sem számítjuk be, melyek q-val oszthatóak (azaz D-t osztjuk a q-val nem osztható Φ-beli elemek Δ* elemrendszerének E szorzatával is), szintén F adódik. Azaz
 , azaz  emiatt  , azaz (leosztva a p modulushoz relatív prím E-vel
  . 

Ki kell számolnunk D-t és E-t.

 D kiszámításakor összeszorozzuk egyrészt a 0, 1, 2, …, p-1 teljes maradékrendszer mod(p) redukált elemeit, aztán a p, p+1, p+2, …, p+(p-1) = 2p-1 halmaz mod(p) redukált elemeit, hasonlóan a 2p, 2p+1, 2p+2, …, 3p-1 halmaz mod(p) redukált elemeit, és így tovább, amíg el nem érjük a (pq-1)/2 számot; aztán a szorzat mod(p) maradékát képezzük. Mivel az összeszorzás és a maradékképzés felcserélhető, végül is azt tesszük, hogy vesszük valahányszor a 0, 1, …, p-1 közti redukált mod(p) maradékrendszert, és annyiszor összeszorozzuk, ahányszor az előbb összeszoroztuk a mod(p) teljes maradékrendszerek elemeit (azaz ahány mod(p) teljes maradékrendszerre bomlik a 0, 1, …, (pq-1)/2 halmaz. Kiszámolható, hogy hányszor kell összeszoroznunk: mivel
  . 

Ezek szerint egyrészt egy mod(p) redukált maradékrendszer elemeit kell mod(p) összeszoroznunk, ami Wilson tétele alapján
  , 
mégpedig ezt q-1-szer, ezen kívül D tényezői még egy 0, 1, 2, …, (p-1)/2 elemű redukált maradékrendszer elemei; minthogy p prím, ezért a fenti halmazból minden szám ilyen; tehát
    . 

 A Δ-beli számok közül vegyük még azok mod(p) szorzatát, melyek q-val oszthatóak, ezek:  , ugyanis a legnagyobb egész szám, mellyel megszorozva q-t még kisebb számot kapunk mint (pq-1)/2, a
            . 

Számoljuk ki a Δ*-beli elemek mod(p) szorzatát, felhasználva, hogy az Euler-kritérium szerint ; ez:
 
      
    . 

Tudva azt, hogy egy Legendre-szimbólum relatív prím változókra mindig ugyanaz, mint reciprokának értéke, hiszen egy Legendre-szimbólum 1, és ekkor reciproka is, vagy -1, és ekkor is reciproka is. Tehát:

        ,
és pontosan ezt szerettük volna belátni.

A segédtételek alkalmazása reciprocitás bizonyítására 

F megoldása a következő szimultán kongruenciarendszernek (de nem kell aggódni, kínai maradéktétel itt nem lesz ):
  
  

Ez azt jelenti, hogy F-et a 0, 1, …, p-1 mod(p) teljes maradékrendszerben az 1 vagy p-1 reprezentálja (hiszen a fenti kifejezések olyan szorzatok, melyek tényezői, azok definíciói miatt, 1 abszolút értékűek). De mivel p-1<pq-1, ezért a 0, 1, … , pq-1 mod(pq) teljes maradékrendszerben is 1 vagy p-1 reprezentálja, hisz a mod(p) standard maradékok egyben mod(pq) standard maradékok is. De ugyanez igaz a 0, 1, …, q-1 teljes maradékrendszerre is: F-et 1 vagy q-1 reprezentálja mod(q), és ezáltal mod(pq) is 1 vagy q-1 reprezentálja.
Ha F-et mod(p) az 1 reprezentálja, akkor a p-1 nem reprezentálhatja, mert ekkor p-1 ≡ 1 mod(p) azaz p ≡ 2 mod(p) ellentmondana annak, hogy p páratlan. Hasonló igaz q-ra. Sőt pq-ra is: például F-et egyszerre nem reprezentálhatja 1 is meg p-1 is, mert akkor utóbbiak kongruensek lennének, azaz p ≡ 2 mod(pq) lenne, azaz p = 2+kpq, ahonnan p(1-kq) = 2 alapján p = 2, ami ellentmond a feltételeknek.
Így a következő, egymást kizáró lehetőségek vannak:
 F mod(p) maradéka 1, akkor mod(pq) maradéka is 1, és így mod(q) maradéka is 1.
 F mod(p) maradéka p-1, akkor mod(pq) maradéka is p-1, akkor nem 1, és így mod(q) maradéka sem 1, tehát csak q-1 lehet.

 Az első eset esetében, ami az 1. lemma szerint csakkor lehetséges, ha p,q is 1-gyel kongruens mod(4), e mod(p) és mod(q) a maradékok mint számok megegyeznek (hiszen 1-gyel egyenlőek), írható hát:
  
Ebből átszorzásokkal és figyelembe véve, hogy a tényezők értéke mindig ugyanaz, mint reciprokuké (mivel értékük ±1), kijön a kvadratikus reciprocitás tétele.
 A második esetben is elérhetünk hasonlót, ha nem a standard, legkisebb abszolútértékű pozitív elemekből álló teljes maradékrendszerekben reprezentáljuk F-et, hanem a legkisebb abszolútértékű negatív elemekből álló teljes maradékrendszerekben. Ekkor a maradékok értékét rögzítettük, és mint számok észrevehetően mind -1-gyel egyenlőek. Innentől kezdve már az előzővel megegyező gondolatmenetet alkalmazva, szintén adódik a kvadratikus reciprocitás tétele.

Ezzel a bizonyítást befejeztük. QED

Lásd még 
 kubikus reciprocitás tétele
 bikvadratikus reciprocitás tétele
 körosztási reciprocitás tétele
 osztálytest-elmélet

Hivatkozások

Források 

 Rövid áttekintés
 Mathworld bejegyzés (angolul)
 Bizonyítások és tudománytörténeti vonatkozások
 A Kvadratikus reciprocitás tételének bizonyításai (angolul)
 Különféle bizonyítások és azok története (angolul)
 Eisenstein „félreértett” geometriai bizonyítása  (angolul)
 A kvadratikus reciprocitás tételének bizonyítása a Boyer-More-féle automatikus tételbizonyító rendszerben (PDF) (angolul)
 Általánosítások
 Egy általánosítás véges csoportokban (angolul) (PDF)
 Egy általánosítás véges testekben (angolul) (PDF)
 Egy általánosítás polinomokra  (angolul) (PDF)

Irodalom 

 S. Y. Kim: An elementary proof of the quadratic reciprocity law. American Math. Monthly, 111 (2004), 48-50.
 Gyarmati Edit: Számelmélet. Turán Pál előadásainak fölhasználásával. Egyetemi jegyzet. Nemzeti tankönyvkiadó, Bp., 1997.
 Szalay Mihály: Számelmélet. Speciális Matematika Tankönyvek sorozat. Nemzeti Tankönyvkiadó, Typotex, 1998. .

Számelméleti tételek
Matematikai tételek