Legendren symboli ja Jacobin symboli sekä niiden ominaisuuksia

Abstract

Tämä tutkielma käsittelee lukuteoriaa. Lukuteoriassa keskitytään kokonaislukujen ominaisuuksiin ja erityisesti alkulukuihin. Tässä tutkielmassa erityisesti kongruenssin käsite on tärkeä. Neliönjäännös ja neliönepäjäännös määritellään niin, että mikäli kokonaislukujen a ja m suurin yhteinen tekijä on 1 ja a toteuttaa yhtälön x² ≡ a (mod m) se on luvun m neliönjäännös ja mikäli ei, niin a on luvun m neliönepäjäännös. Neliönjäännöksiä ja neliönepäjäännöksiä on aina yhtä monta, kun m on pariton alkuluku. Alkuluvuista päästään Legendren symbolin määritelmään. Kun p on positiivinen alkuluku ja a on kokonaisluku, joka ei ole jaollinen luvulla p, niin Legendren symbolin (a/p) arvo on 1 jos a on luvun p neliönjäännös ja -1 jos a on luvun p neliönepäjäännös. Legendren symbolille voidaan johtaa sen arvon määrittämistä helpottavia lauseita, esimerkiksi Eulerin kriteeri. Tämän lisäksi Legendren symbolille pätee esimerkiksi neliöjuurifunktiosta tuttu liitännäisyys tulon suhteen, eli Legendren symbolien tulo saa saman arvon kuin tulon Legendren symboli. Myös keskenään kongruenttien lukujen Legendren symboli saa saman arvon, ja neliön Legendren symbolin arvo on aina 1. Jacobin symboli on Legendren symbolin yleistys, joka pätee kaikille parittomille kokonaisluvuille, eikä vain parittomille alkuluvuille kuten Legendren symboli. Jacobin symbolin määritelmä perustuu siihen, että alkutekijöihin jaettu pariton luku n voidaan jakaa alkutekijöihinsä, eli n=p_1^{t_1}p_2^{t_2} \cdots p_m^{t_m}, missä kaikki luvut p_i ovat alkulukuja ja potenssit kertovat niiden määrän. Tällöin Jacobin symboli (a/n) voidaan esittää Legendren symbolien tulona. Myös Jacobin symbolille pätee liitännäisyys tulon suhteen ja keskenään kongruenttien lukujen Jacobin symboli saa saman arvon. Neliönjäännösten ominaisuuksien avulla voidaan heittää kolikkoa elektronisesti. Tämä perustuu siihen, että neliönjäännöksiä esiintyy aina yhtä monta kuin neliönepäjäännöksiä ja siihen, että jos tietää luvun neliönjäännöksen, niin ei voi silti päätellä mikä luku on kyseessä. Jacobin symbolin avulla voidaan myös suorittaa alkulukutesti. Mikäli aiemmin mainittu Eulerin lause ei päde, niin voidaan suoraan todeta, että tutkittu luku ei ole alkuluku.