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

 \bold{x}^2\equiv p\ ({\rm mod}\ q)     és az      \bold{y}^2\equiv q\ ({\rm mod}\ p)

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 | forrásszöveg szerkesztése]

Kvadratikus maradékok[szerkesztés | forrásszöveg szerkesztése]

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, ellenben 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 | forrásszöveg szerkesztése]

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

 \left( \frac{a}{b} \right) \ := \ \begin{cases} \ \ 0, & \mbox{ha} \ b|a; \\ \ \ 1, & \mbox{ha} \ a \ \mbox{kvadratikus} \ \mathrm{marad \acute e k} \ \mbox{b-re} \ \mathrm{n \acute ezve} \\ -1, & \mbox{ha} \ a \ \mbox{kvadratikus} \ \mbox{nem-marad}\mathrm{ \acute e k} \ \mbox{b-re} \ \mathrm{n \acute ezve} \end{cases}

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

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

 \left(\frac{p}{q}\right) \left(\frac{q}{p}\right) = (-1)^{\frac{(p-1)(q-1)}{4}}

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

 \left(\frac{-1}{p}\right)= (-1)^{\frac{(p-1)}{2}}    és     \left(\frac{2}{p}\right)= (-1)^{\frac{(p^2-1)}{8}}

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ú,  \frac{(p-1)(q-1)}{4} = \frac{[(4u+1)-1][(2v+1)-1]}{4} = \frac{4u \cdot 2v}{4} = 2uv ), í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ő ( \frac{(4u+2)(4v+2)}{4} = 4\frac{(2u+1)(2v+1)}{4} = (2u+1)(2v+1) ) 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 | forrásszöveg szerkesztése]

Elemi bizonyítás[szerkesztés | forrásszöveg szerkesztése]

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:

 \Phi := \left\{ \ f \ | \ 1 \le f \le \frac{pq-1}{2} \ \wedge \ \left( f, pq \right) = 1 \ \right\} és


 F := \prod \Phi = \prod _{f \in \Phi} f .

1. segédtétel[szerkesztés | forrásszöveg szerkesztése]

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

 F \equiv \plusmn 1 \pmod{pq} \Leftrightarrow p \equiv q \equiv 1 \pmod{4}

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 | forrásszöveg szerkesztése]

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

 F \equiv \left( -1 \right) ^{\frac{q-1}{2}} \left( \frac{q}{p} \right) \pmod{p}    és     F \equiv \left( -1 \right) ^{\frac{p-1}{2}} \left( \frac{p}{q} \right) \pmod{q} .

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:

 \left( \frac{a}{p} \right) \equiv a^{ \frac{p-1}{2} }

Legyenek

 \Delta \  :=  \ \left( d \in \ | \ \ 1 \le d \le \frac{pq-1}{2} \ \wedge \ \left( d, p \right) = 1 \ \right) ,

és

 D \  := \ \left( \prod \Delta \right) mod(p) \ = \ \left( \prod_{d \in \Delta} d \right) mod(p) ,

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  F = \frac{D}{E} , azaz  EF = D emiatt  EF \equiv D \pmod{p} , azaz (leosztva a p modulushoz relatív prím E-vel

 F \equiv \frac{D \ mod(p)}{ E \ mod(p)} \pmod{p} .

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

  • D kiszámításakor összeszorozzuk egyrészt az 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
 \frac{pq-1}{2} = \frac{pq}{2}-\frac{1}{2} = \frac{p[(q-1)+1]}{2}-\frac{1}{2} = p \frac{q-1}{2}+\frac{p-1}{2} .

Ezek szerint egyrészt egy mod(p) redukált maradékrendszer elemeit kell mod(p) összeszoroznunk, ami Wilson tétele alapján

 (p-1)! \equiv (-1) \pmod{p} ,

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

 D \equiv \left( p-1 \right)!^{\frac{q-1}{2}} \cdot \prod _{j=1}^{\frac{p-1}{2}}j  \equiv  (-1)^{ \frac{q-1}{2} } \left( \frac{p-1}{2} \right)! \mod{p} .
  • A Δ-beli számok közül vegyük még azok mod(p) szorzatát, melyek q-val oszthatóak, ezek: \Delta ^{*} := \{ q, 2q, 3q, ..., \frac{p-1}{2}q \} , ugyanis a legnagyobb egész szám, mellyel megszorozva q-t még kisebb számot kapunk mint (pq-1)/2, a
 \left \lfloor \frac{ \frac{pq-1}{2} }{q} \right \rfloor  =  \left \lfloor \frac{pq-1}{2q} \right \rfloor  =  \left \lfloor \frac{pq}{2q}-\frac{1}{2q} \right \rfloor  =  \left \lfloor \frac{p}{2}-\frac{1}{2q} \right \rfloor  =  \left \lfloor \frac{p}{2} \right \rfloor  =  \frac{p-1}{2} .

Számoljuk ki a Δ*-beli elemek mod(p) szorzatát, felhasználva, hogy az Euler-kritérium szerint  q^{\frac{p-1}{2}} = \left( \frac{q}{p}\right) ; ez:

 E \ := \ \prod \left( \Delta ^{*} \right) \  =  \prod_{j=1}^{\frac{p-1}{2}} jq  =  q^{\frac{p-1}{2}} \prod_{j=1}^{\frac{p-1}{2}} j  =


 =  q^{\frac{p-1}{2}} \cdot \left( \frac{p-1}{2} \right)!  \equiv \left( \frac{q}{p}\right) \left( \frac{p-1}{2} \right)! \pmod{p} .

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:

 F  \equiv  \frac{D}{E}  \equiv  \frac{(-1)^{ \frac{q-1}{2} } \left( \frac{p-1}{2} \right)! }{\left( \frac{q}{p}\right) \left( \frac{p-1}{2} \right)!}  \equiv  \frac{ (-1)^{ \frac{q-1}{2} } } {\left( \frac{q}{p} \right) }  \equiv (-1)^{ \frac{q-1}{2} } \left( \frac{q}{p} \right) \pmod{p} , és pontosan ezt szerettük volna belátni.

A segédtételek alkalmazása reciprocitás bizonyítására[szerkesztés | forrásszöveg szerkesztése]

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

 F \equiv \left( -1 \right)^{\frac{q-1}{2}}\left( \frac{q}{p} \right) \pmod{p}
 F \equiv \left( -1 \right)^{\frac{p-1}{2}}\left( \frac{p}{q} \right) \pmod{p}

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:
 \left( -1 \right)^{\frac{q-1}{2}}\left( \frac{q}{p} \right) = \left( -1 \right)^{\frac{p-1}{2}}\left( \frac{p}{q} \right)

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 | forrásszöveg szerkesztése]

Hivatkozások[szerkesztés | forrásszöveg szerkesztése]

Források[szerkesztés | forrásszöveg szerkesztése]

Irodalom[szerkesztés | forrásszöveg szerkesztése]

  • 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.