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

${\displaystyle \mathbf {x} ^{2}\equiv p\ ({\rm {mod}}\ q)}$

és az

${\displaystyle \mathbf {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

Kvadratikus maradékok

Ha érvényes

${\displaystyle x^{2}\equiv a{\pmod {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

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

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

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ú, ${\displaystyle {\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ő (${\displaystyle {\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.

A tétel általánosabban igaz Jacobi-szimbólumokra is: ez a Legendre-szimbólum általánosítása.

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:

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:

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

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

1. segédtétel

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

${\displaystyle F\equiv \pm 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 u² ≡ 1 mod(pq) és az v² ≡ -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 w² ≡ 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|w²-1 = (w+1)(w-1) alapján, tekintetbe véve, hogy ${\displaystyle 0\leq w<p-1}$).
  • A w² ≡ -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 m₁, m₂, …, m_q 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 x₀, akkor megoldása, és az eredeti kongruencia megoldása is, a teljes [x₀] mod(M) maradékosztály is, ahol M :=[m₁, …, m_q] 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 u² ≡ 1 mod(pq) kongruenciát, másrészt a v² ≡ -1-et.
    • Az előbbit a kínai maradéktétel szerint visszavezetjük egy szimultán kongruenciarendszer megoldására, nevezetesen az u² ≡ 1 mod(p) és u² ≡ 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 G₁ := ±x.
    • Hasonlóan járunk el az utóbbi, v² ≡ -1 mod(pq) kongruenciával. Visszavezetve a v² ≡ -1 (p) és v² ≡ -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)² = x²y² ≡ 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 G₂ ±y · ±xy = ±x.
    • Ennélfogva G = G₁ · G₂ = ±x · ±x = ± x² = ± 1.
• Fordítva, ha p és q közül nem mindkettő 1-gyel kongruens mod(4) , Ψ csak x² ≡ 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ó:

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

és

${\displaystyle 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:

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

Legyenek

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

és

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

${\displaystyle 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 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

${\displaystyle {\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

${\displaystyle (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

${\displaystyle D\equiv \left(p-1\right)!^{\frac {q-1}{2}}\cdot \prod _{j=1}^{\frac {p-1}{2}}j}$ ${\displaystyle \equiv }$ ${\displaystyle (-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: ${\displaystyle \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

${\displaystyle \left\lfloor {\frac {\frac {pq-1}{2}}{q}}\right\rfloor }$ ${\displaystyle =}$ ${\displaystyle \left\lfloor {\frac {pq-1}{2q}}\right\rfloor }$ ${\displaystyle =}$ ${\displaystyle \left\lfloor {\frac {pq}{2q}}-{\frac {1}{2q}}\right\rfloor }$ ${\displaystyle =}$ ${\displaystyle \left\lfloor {\frac {p}{2}}-{\frac {1}{2q}}\right\rfloor }$ ${\displaystyle =}$ ${\displaystyle \left\lfloor {\frac {p}{2}}\right\rfloor }$ ${\displaystyle =}$ ${\displaystyle {\frac {p-1}{2}}}$ .

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

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

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

${\displaystyle F}$ ${\displaystyle \equiv }$ ${\displaystyle {\frac {D}{E}}}$ ${\displaystyle \equiv }$ ${\displaystyle {\frac {(-1)^{\frac {q-1}{2}}\left({\frac {p-1}{2}}\right)!}{\left({\frac {q}{p}}\right)\left({\frac {p-1}{2}}\right)!}}}$ ${\displaystyle \equiv }$ ${\displaystyle {\frac {(-1)^{\frac {q-1}{2}}}{\left({\frac {q}{p}}\right)}}}$ ${\displaystyle \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

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

${\displaystyle F\equiv \left(-1\right)^{\frac {q-1}{2}}\left({\frac {q}{p}}\right){\pmod {p}}}$ ${\displaystyle 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:

${\displaystyle \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

• kubikus reciprocitás tétele
• bikvadratikus reciprocitás tétele
• körosztási reciprocitás tétele
• osztálytestelmé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 Archiválva 2005. március 10-i dátummal a Wayback Machine-ben (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 Archiválva 2005. január 8-i dátummal a Wayback Machine-ben (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. ISBN 963-9132-25-X.