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
Kirjallisuutta