Kwadratisch residu

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

$x^{2}\equiv q{\pmod {n}}$.

Anders noemt men $q$, behalve voor $x=0$, een kwadratisch non-residu modulo $n$. Het getal 0 wordt voor $x=0$ 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.

Geschiedenis

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 $n$ kan een lijst van kwadratische residuen ${\bmod {n}}$ worden gemaakt door de getallen 0, 1, ..., $n-1$ te kwadrateren. Omdat $a^{2}\equiv (n-a)^{2}{\bmod {n}}$, is de lijst van kwadraten ${\bmod {n}}$ symmetrisch om $n/2$, de lijst hoeft dus eigenlijk alleen tot $n/2$, of voor het geval dat $n$ oneven is tot $(n-1):2$, te gaan.

Er zijn ${\bmod {p}}$, met $p$ een priemgetal, altijd $(p+1):2$ kwadratische residuen en $(p-1):2$ kwadratische non-residuen.

Het product van twee residuen is altijd een residu.

Tabel van kwadratische residuen

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 ${\bmod {4}}$, ${\bmod {8}}$ en ${\bmod {1}}6$ 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