Kvadratikus reciprocitás tétele

A Wikipédiából, a szabad enciklopédiából

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

    és 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[szerkesztés]

Kvadratikus maradékok[szerkesztés]

Ha érvényes

x2 ≡ a mod(b)

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[szerkesztés]

Alkalmazva az ún. Legendre-szimbólumot: ha a egész szám és b>0 prímszám, legyen

a számelmélet eme igen nevezetes tétele azt állítja, hogy:

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

Ide szokás még sorolni az úgynevezett kiegészítő lemmákat:

   és   

ha p páratlan prím.

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[szerkesztés]

Elemi bizonyítás[szerkesztés]

Az alábbi, S.Y. Kimtől származó bizonyítás két segédtételen alapul, nevezetesen:

  1. 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;
  2. 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[szerkesztés]

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[szerkesztés]

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

   és    .

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[szerkesztés]

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:

  1. F mod(p) maradéka 1, akkor mod(pq) maradéka is 1, és így mod(q) maradéka is 1.
  2. 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[szerkesztés]

Hivatkozások[szerkesztés]

Források[szerkesztés]

Irodalom[szerkesztés]

  • 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. ISBN 963-9132-25-X.