neliöresiduista

Neliöresidua on käsite lukuteoriassa, joka liittyy kokonaislukujen jakamiseen. Luku a on neliöresidua modulo m, jos on olemassa sellainen kokonaisluku x, että x² ≡ a (mod m). Toisin sanoen, a on neliöresidua modulo m, jos a on kongruentti jonkin luvun neliön kanssa modulo m. Jos tällaista x ei ole olemassa, a on neliöepäresidua modulo m.

Tarkastellaan esimerkiksi modulo 5. Luvun neliöt modulo 5 ovat:

0² ≡ 0 (mod 5)

1² ≡ 1 (mod 5)

2² ≡ 4 (mod 5)

3² ≡ 9 ≡ 4 (mod 5)

4² ≡ 16 ≡ 1 (mod 5)

Tästä seuraa, että luvut 0, 1 ja 4 ovat neliöresidua modulo 5. Luvut 2 ja 3 ovat neliöepäresidua modulo 5.

Erityistapauksena on alkuluku m. Jos p on alkuluku, niin luku a on neliöresidua modulo p, jos a ei ole jaollinen p:llä ja yhtälöllä x² ≡ a (mod p) on ratkaisu. Jos a on jaollinen p:llä, se on triviaalisti neliöresidua, sillä x=0 toteuttaa x² ≡ 0 (mod p). Usein neliöresidua määritelmässä oletetaan, että a ei ole jaollinen p:llä. Tässä tapauksessa neliöresidua modulo p ovat ne luvut, jotka ovat jaottomia p:n kanssa ja joille on olemassa ratkaisu. Eulerin kriterio antaa tavan määrittää, onko luku a neliöresidua modulo alkuluku p (kun p ei jaa a:ta): 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), niin a on neliöepäresidua modulo p.

Neliöresidujen käsite on tärkeä muun muassa krypto grafiassa ja lukuteorian muissa haaroissa.