Neliönjäännös

Wikipedia
Loikkaa: valikkoon, hakuun

Matematiikassa luku q on neliönjäännös modulo n, jos on olemassa kokonaisluku x, jolle

{x^2}\equiv{q}\mbox{ (mod }n\mbox{)}.

muutoin lukua q sanotaan neliönepäjäännökseksi.

Toisin sanoen neliönjäännös modulo n on luku, jolla on neliöjuuri modulaarisessa aritmetiikassa. Neliönjäännöslause ja Gaussin lemma kertoo hieman lisää neliönjäännösten ja alkulukujen teoriasta. Neliönjäännöksiä käytetään Legendren symbolissa.

Neliönjäännökset ja -epäjäännökset jakaantuvat kahteen osaan. Toisin sanoen jokaiselle alkuluvulle n on olemassa

(n − 1)/2

neliönjäännöstä ja -epäjäännöstä. Se, kumpaan luokkaan tietty luku kuuluu, on varsin sattumanvaraista.

Neliönjäännös modulo n on sellainen luku, jolla on neliöjuuri modulo n. Tätä käsitettä käytetään paljon klassisessa lukuteoriassa.

Neliöjuuren etsiminen modulaariaritmetiikassa, yllä olevan yhtälön ratkaiseminen annetuilla q ja n, on vaikea ongelma. Yleisesti yhdistetylle luvulle n ongelma tiedetään olevan ekvivalentti n:n tekijöihinjaon kanssa. Siten, jos toiseen ongelmaan pystytään kehittämään tehokas ratkaisumenetelmä, samalla pystytään toinenkin ongelma ratkaisemaan tehokkaasti. Toisaalta on NP-täydellinen ongelma selvittää se, onko ongelmalla ratkaisua x<c jollakin annetulla positiivisella kokonaisluvulla c.

Neliönjäännöksillä on keskeinen rooli seuraavissa käsitteissä:

Esimerkkejä[muokkaa | muokkaa wikitekstiä]

Luku 4 on neliönjäännös modulo 5, koska

{3^2}\equiv{4}\mbox{ (mod }5\mbox{)}.

Myös luku 1 on neliönjäännös modulo 5:

{4^2}\equiv{1}\mbox{ (mod }5\mbox{)}.

Sen sijaan luku 3 on epäneliönjäännös modulo 5, koska ei ole olemassa kokonaislukua x, joka toteuttaisi yhtälön

{x^2}\equiv{3}\mbox{ (mod }5\mbox{)}.


Viitteet[muokkaa | muokkaa wikitekstiä]