Kwadratisch residu

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

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

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