Neliönjäännöslause

Lukuteoriassa neliönjäännöslause (myös: neliönjäännösten resiprookkilause) 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 todistuksen lauseelle antoi Gauss vuonna 1796, ollessaan vasta 18-vuotias. Gauss kutsui lausetta kultaiseksi lauseeksi ja tutki lausetta niin innokkaasti, että löysi sille ainakin seitsemän erilaista todistusta. Lause on innostanut matemaatikkoja, ja sille tunnetaan jo yli 200 erilaista todistusta.[1]


Neliönjäännöslause kuuluu seuraavasti. 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 ≡ p   ( m o d   q ) {\displaystyle x^{2}\equiv p\ ({\rm {mod}}\ q)}

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

y 2 ≡ q   ( m o d   p ) {\displaystyle y^{2}\equiv q\ ({\rm {mod}}\ p)}

on ratkaisu y ∈ Z {\displaystyle 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 ≡ p   ( m o d   q ) {\displaystyle x^{2}\equiv p\ ({\rm {mod}}\ q)}

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

y 2 ≡ q   ( m o d   p ) {\displaystyle y^{2}\equiv q\ ({\rm {mod}}\ p)}

ei ole ratkaisua y ∈ Z {\displaystyle y\in \mathbb {Z} } .

Legendren symbolista

Legendren symbolin avulla saadaan:

( a p ) = { 1 j o s   a   o n   n e l i o ¨   m o d u l o   p , 0 j o s   p   j a k a a   a , − 1 m u u t o i n , {\displaystyle \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.}

Neliönjäännöslause voidaan esittää lyhyesti Legendren symbolin avulla:

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

Koska ( p − 1 ) ( q − 1 ) / 4 {\displaystyle (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, ( p q ) ( q p ) {\displaystyle \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.

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.

Lähteet

  1. ↑ Proofs of the Quadratic Reciprocity Law rzuser.uni-heidelberg.de. Viitattu 15.7.2009.

Aiheesta muualla

  • Neliönjäännöslause MathWorldissä.
  • Lauseen kaksi todistusta (Arkistoitu – Internet Archive)