Neliönjäännösten resiprookkilaki: todistus ja sovelluksia
RAJALA, MARIANNA (2009)
RAJALA, MARIANNA
2009
Matematiikka - Mathematics
Informaatiotieteiden tiedekunta - Faculty of Information Sciences
This publication is copyrighted. You may download, display and print it for Your own personal use. Commercial use is prohibited.
Hyväksymispäivämäärä
2009-05-25
Julkaisun pysyvä osoite on
https://urn.fi/urn:nbn:fi:uta-1-19790
https://urn.fi/urn:nbn:fi:uta-1-19790
Tiivistelmä
Olkoot p ja q erisuuria parittomia alkulukuja. Oletetaan silloin, että tiedetään, onko q neliönjäännös modulo p vai neliönepäjäännös modulo p. Tällöin voidaan kysyä, tiedetäänkö silloin, että p on neliönjäännös modulo q tai neliönepäjäännös modulo q.
Euler löysi kokeellisesti tähän kysymykseen myöntävän vastauksen vuonna 1783. Hän ei kuitenkaan pystynyt todistamaan vastausta oikeaksi. Vuonna 1785 Legendre muotoili Eulerin vastauksen uudelleen elegantimpaan lauseen muotoon käyttämällä omalla nimellään kulkevaa symbolia. Tämä lause tunnetaan nykyisin neliönjäännösten resiprookkilakina ja se kertoo, onko kongruenssilla x^2 ≡ q (mod p) ratkaisuja, kun tiedetään, onko kongruenssilla x^2 ≡ p (mod q) ratkaisuja.
Tässä tutkielmassa todistetaan neliönjäännösten resiprookkilaista muoto
(p/q)(q/p) = (-1)^{(p-1)/2 x (q-1)/2}
ja todistetaan se ekvivalentiksi muodon
p ≡ ± q (mod 4a) => (a/p) = (a/q)
kanssa. Lisäksi esitetään lauseen sovelluksia.
Lukijalta edellytetään joidenkin lukuteorian perusasioiden tuntemista. Oletetaan muun muassa, että lukija tuntee jaollisuuden ja suurimman yhteisen tekijän tarkan määritelmän sekä alkuluvun käsitteen. Päälähdeteoksena käytetään Kenneth H. Rosenin kirjaa Elementary number theory and its applications.
Asiasanat:neliönjäännösten resiprookkilaki, Legendren symboli, Jacobin symboli, Pepinin testi, U-matriisi
Euler löysi kokeellisesti tähän kysymykseen myöntävän vastauksen vuonna 1783. Hän ei kuitenkaan pystynyt todistamaan vastausta oikeaksi. Vuonna 1785 Legendre muotoili Eulerin vastauksen uudelleen elegantimpaan lauseen muotoon käyttämällä omalla nimellään kulkevaa symbolia. Tämä lause tunnetaan nykyisin neliönjäännösten resiprookkilakina ja se kertoo, onko kongruenssilla x^2 ≡ q (mod p) ratkaisuja, kun tiedetään, onko kongruenssilla x^2 ≡ p (mod q) ratkaisuja.
Tässä tutkielmassa todistetaan neliönjäännösten resiprookkilaista muoto
(p/q)(q/p) = (-1)^{(p-1)/2 x (q-1)/2}
ja todistetaan se ekvivalentiksi muodon
p ≡ ± q (mod 4a) => (a/p) = (a/q)
kanssa. Lisäksi esitetään lauseen sovelluksia.
Lukijalta edellytetään joidenkin lukuteorian perusasioiden tuntemista. Oletetaan muun muassa, että lukija tuntee jaollisuuden ja suurimman yhteisen tekijän tarkan määritelmän sekä alkuluvun käsitteen. Päälähdeteoksena käytetään Kenneth H. Rosenin kirjaa Elementary number theory and its applications.
Asiasanat:neliönjäännösten resiprookkilaki, Legendren symboli, Jacobin symboli, Pepinin testi, U-matriisi