Neliönjäännös

Wikipediasta
Siirry navigaatioon Siirry hakuun

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

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ä:

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

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

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