Kwadratisch residu

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

Een geheel getal q heet een kwadratisch residu modulo n als het congruent is aan een perfect vierkant (mod n); dat wil zeggen, als er een geheel getal x bestaat zodanig dat:

{x^2}\equiv {q} \pmod{n} \,

Anders noemt men q een kwadratisch non-residue (mod n).

Oorspronkelijk een abstract wiskundig concept uit het deelgebied van de getaltheorie dat bekendstaat als modulair rekenen, worden kwadratische residuen nu gebruikt in toepassingen variërend van akoestische engineering tot cryptografie en de factoring van de grote getallen.

Geschiedenis[bewerken]

Fermat, Euler, Lagrange, Legendre en andere getaltheoretici uit de 17e en 18e eeuw bewezen enkele stellingen [1] en uitten enkele vermoedens[2] over kwadratische residuen, maar de eerste systematische behandeling is §IV van Gauss zijn Disquisitiones Arithmeticae (1801). Artikel 95 introduceert de terminologie "kwadratisch residu" en "kwadratisch non-residu", en stelt dat, indien de context duidelijk is, het bijvoeglijk naamwoord "kwadratisch" geschrapt kan worden geschrapt.

Voor een gegeven n kan een lijst van kwadratische residuen (modn) worden verkregen door de getallen 0, 1, ...,n- 1 simpelweg te kwadrateren. Omdat a2 ≡ (na)2 (mod n), is de lijst van kwadraten (mod n) symmetrisch rond n/2 (de lijst hoeft slechts tot n/2 te gaan). Dit is te zien in de onderstaande tabel.

Zo kan het aantal kwadratische residuen (mod n) niet meer dan n/2 + 1 (n even) of (n + 1)/2 (n oneven) zijn.[3]

Het product van twee residuen is altijd een residu.

Tabel van kwadratische residuen[bewerken]

Kwadratische residuen
x 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
x2 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 2 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1
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 4 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 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 6 1 4 3 4 1 0 1 4 3 4 1 0 1 4 3 4 1 0 1 4 3 4 1 0 1
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 8 1 4 1 0 1 4 1 0 1 4 1 0 1 4 1 0 1 4 1 0 1 4 1 0 1
mod 9 1 4 0 7 7 0 4 1 0 1 4 0 7 7 0 4 1 0 1 4 0 7 7 0 4
mod 10 1 4 9 6 5 6 9 4 1 0 1 4 9 6 5 6 9 4 1 0 1 4 9 6 5
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 12 1 4 9 4 1 0 1 4 9 4 1 0 1 4 9 4 1 0 1 4 9 4 1 0 1
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 14 1 4 9 2 11 8 7 8 11 2 9 4 1 0 1 4 9 2 11 8 7 8 11 2 9
mod 15 1 4 9 1 10 6 4 4 6 10 1 9 4 1 0 1 4 9 1 10 6 4 4 6 10
mod 16 1 4 9 0 9 4 1 0 1 4 9 0 9 4 1 0 1 4 9 0 9 4 1 0 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 18 1 4 9 16 7 0 13 10 9 10 13 0 7 16 9 4 1 0 1 4 9 16 7 0 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 20 1 4 9 16 5 16 9 4 1 0 1 4 9 16 5 16 9 4 1 0 1 4 9 16 5
mod 21 1 4 9 16 4 15 7 1 18 16 16 18 1 7 15 4 16 9 4 1 0 1 4 9 16
mod 22 1 4 9 16 3 14 5 20 15 12 11 12 15 20 5 14 3 16 9 4 1 0 1 4 9
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 24 1 4 9 16 1 12 1 16 9 4 1 0 1 4 9 16 1 12 1 16 9 4 1 0 1
mod 25 1 4 9 16 0 11 24 14 6 0 21 19 19 21 0 6 14 24 11 0 16 9 4 1 0

Voetnoten[bewerken]

  1. Lemmemeyer, Hfdst. 1
  2. Lemmermeyer, blz. 6-8, blz. 16 ev
  3. Gauss, DA, art. 94

Externe links[bewerken]