Neliönjäännös
Wikipedia
Matematiikassa luku q on neliönjäännös modulo n jos on olemassa kokonaisluku x jolle
muutoin q:ta 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öksen 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ä:
- Legendren symboli
- Neliönjäännöslause
- Gaussin lemma
- Zolotarevin lemma
- Paleyn verkko
- neliönjäännösten jakauma
- neliöiden kongruenssi
