Legendren symboli
Legendren symboli on lukuteoriassa symboli , joka kertoo, onko luku neliöjäännös modulo . Toisin sanoen se ilmoittaa, onko olemassa sellainen kokonaisluku b, että
eli b2:stä jää p:llä jaettaessa sama jakojäännös kuin a:stä.
Symbolin otti ensimmäisen kerran käyttöön Adrien-Marie Legendre vuonna 1798 yrittäessään todistaa neliönjäännöslausetta.[1][2]
Määritelmä: Olkoon pariton alkuluku ja kokonaisuluku
Symbolia voidaan merkitä sekä muodossa että .[3]
Esimerkiksi , koska esimerkiksi 42 = 16 on kongruentti 1:n kanssa modulo 5 eli sen jakojäännös 5:llä jaettaessa on 1. Sen sijaan , koska minkään kokonaisluvun neliö ei ole kongruentti 3:n kanssa modulo 5.
Jos alkuluku p on valittu, Legendren symboli käsitettynä a:n funktioksi on jaksollinen, jaksona p. Arvon 0 symboli saa, kun a on tasan jaollinen p:llä.
Eulerin kriteerin mukaan eli ja ovat kongruentteja modulo . [4]
Jacobin symboli on yleistys Legendren symbolista. Se ottaa huomioon myös ne tapaukset joissa alempi luku ei ole alkuluku.[2]
Taulukko symbolin arvoista
Seuraava taulukko osoittaa Legendren symbolin arvot kaikilla kokonaisluvuilla a väliltä 1 … 30 ja alkuluvuilla p, jotka ovat pienempiä kuin 128.
a p | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 | 16 | 17 | 18 | 19 | 20 | 21 | 22 | 23 | 24 | 25 | 26 | 27 | 28 | 29 | 30 |
---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
2 | −1 | 0 | −1 | 0 | −1 | 0 | −1 | 0 | −1 | 0 | −1 | 0 | −1 | 0 | −1 | 0 | −1 | 0 | −1 | 0 | −1 | 0 | −1 | 0 | −1 | 0 | −1 | 0 | −1 | 0 |
3 | −1 | −1 | 0 | −1 | −1 | 0 | 1 | −1 | −0 | 1 | −1 | 0 | 1 | −1 | 0 | −1 | −1 | 0 | 1 | −1 | 0 | 1 | −1 | 0 | −1 | −1 | 0 | 1 | −1 | 0 |
5 | 1 | −1 | −1 | 1 | 0 | 1 | −1 | −1 | 1 | 0 | 1 | −1 | −1 | 1 | 0 | 1 | −1 | −1 | 1 | 0 | 1 | −1 | −1 | 1 | 0 | 1 | −1 | −1 | 1 | 0 |
7 | 1 | 1 | −1 | 1 | −1 | −1 | 0 | 1 | 1 | −1 | 1 | −1 | −1 | 0 | 1 | 1 | −1 | 1 | −1 | −1 | 0 | 1 | 1 | −1 | 1 | −1 | −1 | 0 | 1 | 1 |
11 | 1 | −1 | 1 | 1 | 1 | −1 | −1 | −1 | 1 | −1 | 0 | 1 | −1 | 1 | 1 | 1 | −1 | −1 | −1 | 1 | −1 | 0 | 1 | −1 | 1 | 1 | 1 | −1 | −1 | −1 |
13 | 1 | −1 | 1 | 1 | −1 | −1 | −1 | −1 | 1 | 1 | −1 | 1 | 0 | 1 | −1 | 1 | 1 | −1 | −1 | −1 | −1 | 1 | 1 | −1 | 1 | 0 | 1 | −1 | 1 | 1 |
17 | 1 | 1 | −1 | 1 | −1 | −1 | −1 | 1 | 1 | −1 | −1 | −1 | 1 | −1 | 1 | 1 | 0 | 1 | 1 | −1 | 1 | −1 | −1 | −1 | 1 | 1 | −1 | −1 | −1 | 1 |
19 | 1 | −1 | −1 | 1 | 1 | 1 | 1 | −1 | 1 | −1 | 1 | −1 | −1 | −1 | −1 | 1 | 1 | −1 | 0 | 1 | −1 | −1 | 1 | 1 | 1 | 1 | −1 | 1 | −1 | 1 |
23 | 1 | 1 | 1 | 1 | −1 | 1 | −1 | 1 | 1 | −1 | −1 | 1 | 1 | −1 | −1 | 1 | −1 | 1 | −1 | −1 | −1 | −1 | 0 | 1 | 1 | 1 | 1 | −1 | 1 | −1 |
29 | 1 | −1 | −1 | 1 | 1 | 1 | 1 | −1 | 1 | −1 | −1 | −1 | 1 | −1 | −1 | 1 | −1 | −1 | −1 | 1 | −1 | 1 | 1 | 1 | 1 | −1 | −1 | 1 | 0 | 1 |
31 | 1 | 1 | −1 | 1 | 1 | −1 | 1 | 1 | 1 | 1 | −1 | −1 | −1 | 1 | −1 | 1 | −1 | 1 | 1 | 1 | −1 | −1 | −1 | −1 | 1 | −1 | −1 | 1 | −1 | −1 |
37 | 1 | −1 | 1 | 1 | −1 | −1 | 1 | −1 | 1 | 1 | 1 | 1 | −1 | −1 | −1 | 1 | −1 | −1 | −1 | −1 | 1 | −1 | −1 | −1 | 1 | 1 | 1 | 1 | −1 | 1 |
41 | 1 | 1 | −1 | 1 | 1 | −1 | −1 | 1 | 1 | 1 | −1 | −1 | −1 | −1 | −1 | 1 | −1 | 1 | −1 | 1 | 1 | −1 | 1 | −1 | 1 | −1 | −1 | −1 | −1 | −1 |
43 | 1 | −1 | −1 | 1 | −1 | 1 | −1 | −1 | 1 | 1 | 1 | −1 | 1 | 1 | 1 | 1 | 1 | −1 | −1 | −1 | 1 | −1 | 1 | 1 | 1 | −1 | −1 | −1 | −1 | −1 |
47 | 1 | 1 | 1 | 1 | −1 | 1 | 1 | 1 | 1 | −1 | −1 | 1 | −1 | 1 | −1 | 1 | 1 | 1 | −1 | −1 | 1 | −1 | −1 | 1 | 1 | −1 | 1 | 1 | −1 | −1 |
53 | 1 | −1 | −1 | 1 | −1 | 1 | 1 | −1 | 1 | 1 | 1 | −1 | 1 | −1 | 1 | 1 | 1 | −1 | −1 | −1 | −1 | −1 | −1 | 1 | 1 | −1 | −1 | 1 | 1 | −1 |
59 | 1 | −1 | 1 | 1 | 1 | −1 | 1 | −1 | 1 | −1 | −1 | 1 | −1 | −1 | 1 | 1 | 1 | −1 | 1 | 1 | 1 | 1 | −1 | −1 | 1 | 1 | 1 | 1 | 1 | −1 |
61 | 1 | −1 | 1 | 1 | 1 | −1 | −1 | −1 | 1 | −1 | −1 | 1 | 1 | 1 | 1 | 1 | −1 | −1 | 1 | 1 | −1 | 1 | −1 | −1 | 1 | −1 | 1 | −1 | −1 | −1 |
67 | 1 | −1 | −1 | 1 | −1 | 1 | −1 | −1 | 1 | 1 | −1 | −1 | −1 | 1 | 1 | 1 | 1 | −1 | 1 | −1 | 1 | 1 | 1 | 1 | 1 | 1 | −1 | −1 | 1 | −1 |
71 | 1 | 1 | 1 | 1 | 1 | 1 | −1 | 1 | 1 | 1 | −1 | 1 | −1 | −1 | 1 | 1 | −1 | 1 | 1 | 1 | −1 | −1 | −1 | 1 | 1 | −1 | 1 | −1 | 1 | 1 |
73 | 1 | 1 | 1 | 1 | −1 | 1 | −1 | 1 | 1 | −1 | −1 | 1 | −1 | −1 | −1 | 1 | −1 | 1 | 1 | −1 | −1 | −1 | 1 | 1 | 1 | −1 | 1 | −1 | −1 | −1 |
79 | 1 | 1 | −1 | 1 | 1 | −1 | −1 | 1 | 1 | 1 | 1 | −1 | 1 | −1 | −1 | 1 | −1 | 1 | 1 | 1 | 1 | 1 | 1 | −1 | 1 | 1 | −1 | −1 | −1 | −1 |
83 | 1 | −1 | 1 | 1 | −1 | −1 | 1 | −1 | 1 | 1 | 1 | 1 | −1 | −1 | −1 | 1 | 1 | −1 | −1 | −1 | 1 | −1 | 1 | −1 | 1 | 1 | 1 | 1 | 1 | 1 |
89 | 1 | 1 | −1 | 1 | 1 | −1 | −1 | 1 | 1 | 1 | 1 | −1 | −1 | −1 | −1 | 1 | 1 | 1 | −1 | 1 | 1 | 1 | −1 | −1 | 1 | −1 | −1 | −1 | −1 | −1 |
97 | 1 | 1 | 1 | 1 | −1 | 1 | −1 | 1 | 1 | −1 | 1 | 1 | −1 | −1 | −1 | 1 | −1 | 1 | −1 | −1 | −1 | 1 | −1 | 1 | 1 | −1 | 1 | −1 | −1 | −1 |
101 | 1 | −1 | −1 | 1 | 1 | 1 | −1 | −1 | 1 | −1 | −1 | −1 | 1 | 1 | −1 | 1 | 1 | −1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | −1 | −1 | −1 | −1 | 1 |
103 | 1 | 1 | −1 | 1 | −1 | −1 | 1 | 1 | 1 | −1 | −1 | −1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | −1 | −1 | −1 | 1 | −1 | 1 | 1 | −1 | 1 | 1 | 1 |
107 | 1 | −1 | 1 | 1 | −1 | −1 | −1 | −1 | 1 | 1 | 1 | 1 | 1 | 1 | −1 | 1 | −1 | −1 | 1 | −1 | −1 | −1 | 1 | −1 | 1 | −1 | 1 | −1 | 1 | 1 |
109 | 1 | −1 | 1 | 1 | 1 | −1 | 1 | −1 | 1 | −1 | −1 | 1 | −1 | −1 | 1 | 1 | −1 | −1 | −1 | 1 | 1 | 1 | −1 | −1 | 1 | 1 | 1 | 1 | 1 | −1 |
113 | 1 | 1 | −1 | 1 | −1 | −1 | 1 | 1 | 1 | −1 | 1 | −1 | 1 | 1 | 1 | 1 | −1 | 1 | −1 | −1 | −1 | 1 | −1 | −1 | 1 | 1 | −1 | 1 | −1 | 1 |
127 | 1 | 1 | −1 | 1 | −1 | −1 | −1 | 1 | 1 | −1 | 1 | −1 | 1 | −1 | 1 | 1 | 1 | 1 | 1 | −1 | 1 | 1 | −1 | −1 | 1 | 1 | −1 | −1 | −1 | 1 |
Lähteet
- ↑ Thompson, Jan, 1936-: Matematiikan käsikirja. Helsinki: Tammi, 1994. 186260492. ISBN 951-31-0471-0, 978-951-31-0471-9. Teoksen verkkoversio (viitattu 17.7.2020).
- ↑ a b Anna Kolehmainen: Johdatus neliöjäännöksiin, Pro gradu 2018. Oulun yliopisto, matemaattisten tieteiden laitos.
- ↑ Eric W. Weisstein: Legendre Symbol mathworld.wolfram.com. Viitattu 17.7.2020. (englanniksi)
- ↑ Matematiikan verkkosanakirja matematiikkalehtisolmu.fi. Viitattu 17.7.2020.
Kirjallisuutta
- Thompson, Jan & Martinsson, Thomas: Matematiikan käsikirja, s. 276–277. Suomentanut Virpi Kauko. Helsinki: Tammi, 1994. ISBN 951-31-0471-0.