Legendren symboli

Legendren symboli on lukuteoriassa symboli $\left({\frac {a}{p}}\right)$ , joka kertoo, onko luku $a$ neliöjäännös modulo $p$ . Toisin sanoen se ilmoittaa, onko olemassa sellainen kokonaisluku b, että

{b^{2}}\equiv {a}{\mbox{ (mod }}p{\mbox{)}}

eli b²: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 $p$ pariton alkuluku ja $a$ kokonaisuluku

$\left({\frac {a}{p}}\right)=(a\mid p)={\begin{cases}1&{\text{ jos }}a{\text{ on neliöjäännös modulo }}p{\text{ ja }}a\not \equiv 0{\pmod {p}},\\-1&{\text{muussa tapauksessa, eli jos }}a{\text{ ei ole neliöjäännös modulo }}p,\\0&{\text{jos }}a\equiv 0{\pmod {p}}\end{cases}}$

Symbolia voidaan merkitä sekä muodossa $\left({\frac {a}{p}}\right)$ että $(a\mid p)$ .^[3]

Esimerkiksi $\left({\frac {1}{5}}\right)=1$ , koska esimerkiksi 4² = 16 on kongruentti 1:n kanssa modulo 5 eli sen jakojäännös 5:llä jaettaessa on 1. Sen sijaan $\left({\frac {3}{5}}\right)=-1$ , koska minkään kokonaisluvun neliö ei ole kongruentti 3:n kanssa modulo 5.

Jos alkuluku p on valittu, Legendren symboli $\left({\frac {1}{5}}\right)=1$ käsitettynä a:n funktioksi on jaksollinen, jaksona p. Arvon 0 symboli saa, kun a on tasan jaollinen p:llä.

Eulerin kriteerin mukaan ${\frac {a}{p}}\equiv a^{\frac {p-1}{2}}{\pmod {p}}$ eli ${\frac {a}{p}}$ ja $a^{\frac {p-1}{2}}$ ovat kongruentteja modulo $p$ . ^[4]

Jacobin symboli $\left({\frac {a}{n}}\right)$ on yleistys Legendren symbolista. Se ottaa huomioon myös ne tapaukset joissa alempi luku ei ole alkuluku.^[2]

Taulukko symbolin arvoista muokkaa

Seuraava taulukko osoittaa Legendren symbolin $\left({\frac {a}{p}}\right)$ 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 muokkaa

↑ 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 muokkaa

Thompson, Jan & Martinsson, Thomas: Matematiikan käsikirja, s. 276–277. Suomentanut Virpi Kauko. Helsinki: Tammi, 1994. ISBN 951-31-0471-0.

[1] 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).

[:0-2] Anna Kolehmainen: Johdatus neliöjäännöksiin, Pro gradu 2018. Oulun yliopisto, matemaattisten tieteiden laitos.

[:1-3] Eric W. Weisstein: Legendre Symbol mathworld.wolfram.com. Viitattu 17.7.2020. (englanniksi)

[4] Matematiikan verkkosanakirja matematiikkalehtisolmu.fi. Viitattu 17.7.2020.

[1]

[2]

[3]

[4]