Legendren symboli

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

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

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 p {\displaystyle p} pariton alkuluku ja a {\displaystyle a} kokonaisuluku

( a p ) = ( a ∣ p ) = { 1  jos  a  on neliöjäännös modulo  p  ja  a ≢ 0 ( mod p ) , − 1 muussa tapauksessa, eli jos  a  ei ole neliöjäännös modulo  p , 0 jos  a ≡ 0 ( mod p ) {\displaystyle \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 ( a p ) {\displaystyle \left({\frac {a}{p}}\right)} että ( a ∣ p ) {\displaystyle (a\mid p)} .[3]

Esimerkiksi ( 1 5 ) = 1 {\displaystyle \left({\frac {1}{5}}\right)=1} , koska esimerkiksi 42 = 16 on kongruentti 1:n kanssa modulo 5 eli sen jakojäännös 5:llä jaettaessa on 1. Sen sijaan ( 3 5 ) = − 1 {\displaystyle \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 ( 1 5 ) = 1 {\displaystyle \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 a p ≡ a p − 1 2 ( mod p ) {\displaystyle {\frac {a}{p}}\equiv a^{\frac {p-1}{2}}{\pmod {p}}} eli a p {\displaystyle {\frac {a}{p}}} ja a p − 1 2 {\displaystyle a^{\frac {p-1}{2}}} ovat kongruentteja modulo p {\displaystyle p} . [4]

Jacobin symboli ( a n ) {\displaystyle \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

Seuraava taulukko osoittaa Legendren symbolin ( a p ) {\displaystyle \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

  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).
  2. ↑ a b Anna Kolehmainen: Johdatus neliöjäännöksiin, Pro gradu 2018. Oulun yliopisto, matemaattisten tieteiden laitos.
  3. ↑ Eric W. Weisstein: Legendre Symbol mathworld.wolfram.com. Viitattu 17.7.2020. (englanniksi)
  4. ↑ 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.