Kwadratische reciprociteit

Uit Wikipedia, de vrije encyclopedie
Ga naar: navigatie, zoeken

De wet van de kwadratische reciprociteit is een stelling uit het modulair rekenen, een deelgebied van de getaltheorie, die voorwaarden geeft voor de oplosbaarheid van kwadratische vergelijkingen modulo priemgetallen. Er zijn een aantal gelijkwaardige verklaringen van de stelling, die bestaat uit twee "supplementen" en de kwadratische reciprociteitenwet:

Laat p, q > 2 twee verschillende (positieve oneven) priemgetallen zijn. dan geldt

(Supplement 1)

x2 ≡ −1 (mod p) is oplosbaar dan en slechts dan als p ≡ 1 (mod 4).

(Supplement 2)

x2 ≡ 2 (mod p) is oplosbaar dan en slechts dan als p ≡ ± 1 (mod 8).

(Kwadratische reciprociteit)
Laat q * = ±q   waar het teken positief is als q ≡ 1 (mod 4) en negatief is als q ≡ -1 (mod 4). (Dat wil zeggen |q *| = q en q * ≡ 1 (mod 4).) Dan geldt dat

x2p (mod q) oplosbaar is dan en slechts dan als x2q * (mod p) oplosbaar is.

Hoewel de wet kan worden gebruikt om te vertellen of een kwadratische vergelijking modulo een priemgetal een oplossing heeft, biedt het geen enkele hulp voor het echt vinden van deze oplossing. (Het artikel over kwadratische residuen bespreekt hier algoritmen voor).

Het vermoeden, dat aan de stelling voorafging, werd door Euler en Legendre geuit. De stelling werd als eerste bewezen door Gauss[1]. Gauss verwijst in de Disquisitiones Arithmeticae en zijn nagelaten werk naar deze stelling als de 'fundamentele stelling'. In de privesfeer had hij het over de 'gouden stelling'[2]. Hij publiceerde zes bewijzen, en twee meer werden in zijn nagelaten papieren gevonden. Er zijn nu meer dan 200[3] gepubliceerde bewijzen.

Het eerste deel van dit artikel maakt geen gebruik van de Legendre-symbool en geeft de formuleringen van kwadratische reciprociteit zoals deze zijn geformuleerd door Legendre en Gauss. Het Legendre-Jacobi-symbool werd geïntroduceerd in de tweede paragraaf.

Terminologie, data en twee formuleringen van de stelling[bewerken]

Een kwadratisch residu (modulo n) is elk getal congruent aan een kwadraat (modulo n). Een kwadratisch niet-residu (modulo n) is elk getal dat niet congruent is aan een kwadraat (modulo n). Het bijvoeglijk naamwoord "kwadratisch" kan weggelaten worden als uit de context duidelijk is dat dit wordt geïmpliceerd. Bij het werken met modulo priemgetallen (zoals in dit artikel), is het gebruikelijk om nul als een speciaal geval te behandelen. Door dit te doen, worden de volgende stellingen waar:

  • Modulo een priemgetal, zijn er een gelijk aantal kwadratische residuen en kwadratische niet-residuen.
  • Modulo een priemgetal, is het product van twee kwadratische residuen een kwadratisch residu, het product van een residu en een niet-residu een niet-residu, en het product van twee niet-residuen een residu.

Tabel van kwadratische residuen[bewerken]

Kwadraten modulo priemgetallen
n 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25
n2 1 4 9 16 25 36 49 64 81 100 121 144 169 196 225 256 289 324 361 400 441 484 529 576 625
mod 3 1 1 0 1 1 0 1 1 0 1 1 0 1 1 0 1 1 0 1 1 0 1 1 0 1
mod 5 1 4 4 1 0 1 4 4 1 0 1 4 4 1 0 1 4 4 1 0 1 4 4 1 0
mod 7 1 4 2 2 4 1 0 1 4 2 2 4 1 0 1 4 2 2 4 1 0 1 4 2 2
mod 11 1 4 9 5 3 3 5 9 4 1 0 1 4 9 5 3 3 5 9 4 1 0 1 4 9
mod 13 1 4 9 3 12 10 10 12 3 9 4 1 0 1 4 9 3 12 10 10 12 3 9 4 1
mod 17 1 4 9 16 8 2 15 13 13 15 2 8 16 9 4 1 0 1 4 9 16 8 2 15 13
mod 19 1 4 9 16 6 17 11 7 5 5 7 11 17 6 16 9 4 1 0 1 4 9 16 6 17
mod 23 1 4 9 16 2 13 3 18 12 8 6 6 8 12 18 3 13 2 16 9 4 1 0 1 4
mod 29 1 4 9 16 25 7 20 6 23 13 5 28 24 22 22 24 28 5 13 23 6 20 7 25 16
mod 31 1 4 9 16 25 5 18 2 19 7 28 20 14 10 8 8 10 14 20 28 7 19 2 18 5
mod 37 1 4 9 16 25 36 12 27 7 26 10 33 21 11 3 34 30 28 28 30 34 3 11 21 33
mod 41 1 4 9 16 25 36 8 23 40 18 39 21 5 32 20 10 2 37 33 31 31 33 37 2 10
mod 43 1 4 9 16 25 36 6 21 38 14 35 15 40 24 10 41 31 23 17 13 11 11 13 17 23
mod 47 1 4 9 16 25 36 2 17 34 6 27 3 28 8 37 21 7 42 32 24 18 14 12 12 14

Bovenstaande tabel is compleet voor de priemgetallen kleiner dan 50. Om te controleren of een getal n een kwadratisch residu modulo één van deze priemgetallen p is, vind an (modulo p) en 0 ≤ a < p. Als a in de rij p voorkomt, is het een residu (modulo p); als het niet in de rij p van de tabel voorkomt, is het een niet-residu (modulo p).

De kwadratische reciprociteitswet is de stelling dat bepaalde patronen die in de tabel worden gevonden in het algemeen waar zijn.

In dit artikel verwijzen p en q altijd naar verschillende positieve oneven priemgetallen.

–1 en het eerste supplement[bewerken]

Allereerst vragen we ons af voor welke priemgetallen -1 een kwadratisch residu is? Wanneer we de tabel onderzoeken vinden we -1 in de rijen 5, 13, 17, 29, 37 en 41, maar niet in de rijen 3, 7, 11, 19, 23, 31, 43 of 47.

(–1 ≡ 2 (mod 3),  –1 ≡ 4 (mod 5),   –1 ≡ 10 (mod 11),  etc.)

De eerstgenoemde priemgetallen zijn allen ≡ 1 (mod 4), en de laatstgenoemde priemgetallen zijn allen ≡ 3 (mod 4). Dit leidt tot de zogenaamde eerste supplement van de kwadratische reciprociteit:


\mbox{De congruentie }x^2 \equiv -1 \pmod p \mbox{ is dan en slechts dan oplosbaar als  }p\equiv 1 \pmod 4.

Voetnoten[bewerken]

  1. Gauss, DA § 4, arts 107-150
  2. Bijvoorbeeld in zijn wiskundige dagboek voor 8 april, 1796 (de datum waarop hij voor het eerst bewezen kwadratische reciprociteit). Zie facsimile-pagina van Felix Kleins Development of Mathematics in the 19th Century (Ontwikkeling van de wiskunde in de 19e eeuw)
  3. Zie F. Lemmermeyers chronologie en bibliografie van bewijzen voor kwadratische reciprociteit in de externe verwijzingen

Externe link[bewerken]