Neliöresiduot

Neliöresiduot ovat keskeinen käsite lukuteoriassa. Luku a on kongruenssin x^2 ≡ a (mod m) neliöresidua, jos kongruenssilla on ratkaisu. Toisin sanoen, luku a on neliöresidua modulo m, jos on olemassa kokonaisluku x siten, että x^2 ja a antavat saman jakojäännöksen jaettaessa luvulla m. Jos tällaista x:ää ei ole olemassa, a on neliöepäresidua modulo m.

Tarkastellaan esimerkiksi modulo 5. Neliöjäännökset modulo 5 saadaan laskemalla eri kokonaislukujen neliöt modulo 5:

0^2 ≡ 0 (mod 5)

1^2 ≡ 1 (mod 5)

2^2 ≡ 4 (mod 5)

3^2 ≡ 9 ≡ 4 (mod 5)

4^2 ≡ 16 ≡ 1 (mod 5)

Koska toistuvat jäännökset saadaan jo muutamalla ensimmäisellä kokonaisluvulla, neliöresiduut modulo 5 ovat {0, 1, 4}. Muut luvut, kuten 2 ja 3, ovat neliöepäresidua modulo 5.

Erityisen tärkeä tapaus on alkuluku m = p. Tällöin puhutaan neliöresiduista modulo p. Eulerin kriterio antaa tavan määrittää, onko kokonaisluku a neliöresidua modulo alkuluku p (kun p ei jaa a:ta). Kriteerin mukaan a on neliöresidua modulo p, jos ja vain jos a^((p-1)/2) ≡ 1 (mod p). Jos a^((p-1)/2) ≡ -1 (mod p), a on neliöepäresidua. Jos a on jaollinen p:llä, se on kongruentti 0:n kanssa, joka on aina neliöresidua.

Neliöresiduoiden teoria on perustavanlaatuinen monissa lukuteorian sovelluksissa, kuten toisen asteen kääntyisyyden laissa ja polynomi-kongruenssien ratkaisemisessa.