Neliönjäännöslause

Wikipedia

Lukuteoriassa neliönjäännöslause yhdistää kahden toisen asteen modulaarisen yhtälön ratkeavuuden. Se myös tarjoaa keinon ratkaista jokainen toisen asteen yhtälö modulaarisessa aritmetiikassa

Lauseen otaksuivat Euler ja Legendre ja ensimmäisen tyydyttävän todistuksen lauseelle antoi Gauss. Gauss kutsui lausetta kultaiseksi lauseeksi ja tutki lausetta niin innokkaasti, että löysi sille ainakin seitsemän erilaista todistusta.

Olkoon p ja q kaksi erisuurta paritonta alkulukua. Tällöin p ja q ovat kongruentteja joko 1:n tai 3:n kanssa modulo 4. Jos vähintään toinen näistä luvuista on kongruentti 1:n kanssa modulo 4, on kongruenssilla

$x^2\equiv p\ ({\rm mod}\ q)$

ratkaisu $x\in\mathbb{Z}$ jos ja vain jos kongruenssilla

$y^2\equiv q\ ({\rm mod}\ p)$

on ratkaisu $y\in\mathbb{Z}$ . (Ratkaisut ovat yleensä erisuuria.) Toisaalta jos luvut p ja q ovat molemmat alkulukuja jotka ovat kongruentteja 3:n kanssa modulo 4, on kongruenssilla

$x^2\equiv p\ ({\rm mod}\ q)$

ratkaisu $x\in\mathbb{Z}$ jos ja vain jos kongruenssilla

$y^2\equiv q\ ({\rm mod}\ p)$

ei ole ratkaisua $y\in\mathbb{Z}$ .

[muokkaa] Legendren symboleista

Legendren symbolin avulla saadaan:

$\left(\frac{a}{p}\right)=\left\{\begin{matrix}1 & \mathrm{jos}\ a\ \mathrm{on\ neli\ddot o\ modulo\ }p, \\ 0 & \mathrm{jos\ } p\ \mathrm{jakaa\ }a, \\ -1 & \mathrm{muutoin,}\end{matrix}\right.$

Nämä lauseet voidaan yhdistää:

$\left(\frac{p}{q}\right) \left(\frac{q}{p}\right) = (-1)^{(p-1)(q-1)/4}.$

Koska $(p - 1)(q - 1) / 4$ on parillinen jos joko p tai q on kongruentti 1 mod 4, ja pariton jos ja vain jos molemmat p ja q ovat kongruentteja 3 mod 4, $\left(\frac{p}{q}\right) \left(\frac{q}{p}\right)$ on 1 jos joko p tai q on kongruentti 1 mod 4, ja on yhtäsuuri kuin –1 jos molemmat p ja q ovat kongruentteja 3 mod 4.

Franz Lemmermeyerin kirja Reciprocity Laws: From Euler to Eisenstein, julkaistu vuonna 2000, sisältää viitteen 196 erilaiseen neliönjäännöslauseen todistukseen.

Neliönjäännöslause voidaan yleistää korkeammille potensseille kuin 2, mutta koska kaksi luvun 1 kuutiojuurista ovat kompleksilukuja, kuutionjäännöslause sisältää välttämättä muitakin kuin rationaalilukuja. Sama pätee kolmosta suuremmillekin potensseille.

Gaussin lemma kertoo neliönjäännösten ominaisuuksista ja Gauss käytti lemmaansa kahdessa neliönjäännöslauseen todistuksessaan.