Neliöresidua

Neliöresidua ovat kokonaisluvut, jotka ovat kongruentteja jonkin kokonaisluvun neliön kanssa modulo jokin toinen kokonaisluku. Toisin sanoen, luku $a$ on neliöresidua modulo $n$, jos on olemassa kokonaisluku $x$ siten, että $x^2 \equiv a \pmod{n}$. Jos tällaista $x$:ää ei ole olemassa, $a$ on neliöepäresidua modulo $n$.

Tarkastellaan esimerkiksi modulo 5:

$0^2 \equiv 0 \pmod{5}$

$1^2 \equiv 1 \pmod{5}$

$2^2 \equiv 4 \pmod{5}$

$3^2 \equiv 9 \equiv 4 \pmod{5}$

$4^2 \equiv 16 \equiv 1 \pmod{5}$

Tässä tapauksessa neliöresidut modulo 5 ovat 0, 1 ja 4. Luvut 2 ja 3 ovat neliöepäresidua modulo 5. On huomattava, että vain luvut välillä 0 ja $n-1$ tarvitsee tarkistaa neliöitä modulo $n$, koska $(x+kn)^2 \equiv x^2 \pmod{n}$ kaikilla kokonaisluvuilla $x$, $k$ ja $n$.

Jos $n$ on alkuluku, kuten 5 yllä, silloin ei-nolla neliöresidut modulo $n$ ovat ne luvut $a$, joille Legendre-symboli $(\frac{a}{n})$ on 1. Legendre-symboli määritellään $(\frac{a}{p}) = 1$, jos $a$ on neliöresidua modulo alkuluku $p$ ja $a \not\equiv 0 \pmod{p}$, $(\frac{a}{p}) = -1$, jos $a$ on neliöepäresidua modulo $p$, ja $(\frac{a}{p}) = 0$, jos $a \equiv 0 \pmod{p}$.

Neliöresidujen käsitettä käytetään laajasti lukuteoriassa, erityisesti diofanttisten yhtälöiden ratkaisemisessa ja alkulukujen ominaisuuksien tutkimisessa. Esimerkiksi neliöresidut liittyvät läheisesti neliöjuuren olemassaoloon modulo $n$.