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\text{ (mod }p\text{)}$

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.

Määritelmä: Olkoon $p$ pariton alkuluku ja $a$ kokonaisuluku

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

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

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}}(\mathrm{mod}p)$ eli $\frac{a}{p}$ ja $a^{\frac{p-1}{2}}$ ovat kongruentteja modulo $p$.

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

Taulukko symbolin arvoista

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	Malline:01	0	Malline:01	0	Malline:01	0	Malline:01	0	Malline:01	0	Malline:01	0	Malline:01	0	Malline:01	0	Malline:01	0	Malline:01	0	Malline:01	0	Malline:01	0	Malline:01	0	Malline:01	0	Malline:01	0
3	Malline:01	−1	0	Malline:01	−1	0	1	−1	Malline:00	1	−1	0	1	−1	0	Malline:01	−1	0	1	−1	0	1	−1	0	Malline:01	−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

Kirjallisuutta

• Malline:Kirjaviite