Kwadratisch residu

Een geheel getal heet een kwadratisch residu modulo als het modulo congruent is aan een kwadraat, dat wil zeggen als er een geheel getal bestaat zodanig dat:

.

Anders noemt men , behalve voor , een kwadratisch non-residu modulo . Het getal 0 wordt voor noch als kwadratisch residu, noch als kwadratisch non-residu gerekend.

Het was oorspronkelijk een abstract begrip in de wiskunde uit het deelgebied van de getaltheorie dat bekendstaat als modulair rekenen, maar tegenwoordig worden kwadratische residuen gebruikt in toepassingen variërend van akoestische technologie tot cryptografie. Kwadratische residuen worden veel gebruikt bij het ontbinden in priemfactoren van grote getallen.

GeschiedenisBewerken

Fermat, Euler, Lagrange, Legendre en andere wiskundigen uit de 17e en 18e eeuw bewezen enkele stellingen en brachten enkele vermoedens over kwadratische residuen naar voren, maar de eerste systematische behandeling werd door Gauss in §IV in zijn Disquisitiones Arithmeticae gegeven uit 1801. Hij noemde daar in artikel 95 'kwadratisch residu' en 'kwadratisch non-residu', en stelde dat, indien het uit de context duidelijk is, het bijvoeglijk naamwoord 'kwadratisch' kan worden weggelaten.

Voor een gegeven   kan een lijst van kwadratische residuen   worden gemaakt door de getallen 0, 1, ...,   te kwadrateren. Omdat  , is de lijst van kwadraten   symmetrisch om  , de lijst hoeft dus eigenlijk alleen tot  , of voor het geval dat   oneven is tot  , te gaan.

Er zijn  , met   een priemgetal, altijd   kwadratische residuen en   kwadratische non-residuen.

Het product van twee residuen is altijd een residu.

Tabel van kwadratische residuenBewerken

Het patroon herhaalt zich in iedere rij vanaf de plaats waar er geen waarden meer staan ingevuld. Merk op dat iedere rij in zichzelf symmetrisch is. Bij rekenen  ,   en   herhaalt zich al eerder een patroon in de rij.

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