Legendren symboli

Kokeneet kirjoittajat eivät ole vielä tarkistaneet sivun nykyistä versiota, ja se voi poiketa merkittävästi 28.10.2021 tarkistetusta versiosta . vahvistus vaatii 1 muokkauksen .

Legendre-symboli on lukuteoriassa käytetty funktio . Esitteli ranskalainen matemaatikko A. M. Legendre . Legendre-symboli on erikoistapaus Jacobi-symbolista , joka puolestaan on erikoistapaus Kronecker-Jacobi-symbolista , jota joskus kutsutaan Legendre-Jacobi-Kronecker-symboliksi.

Määritelmä

Olkoon a kokonaisluku ja p muu kuin 2. Legendre -symboli määritellään seuraavasti: $\textstyle \left({\frac {a}{p}}\oikea)$

$\textstyle \left({\frac {a}{p}}\right)=0$ , jos a on jaollinen p :llä ;
$\textstyle \left({\frac {a}{p}}\right)=1$ , jos a on neliöllinen jäännös modulo p (eli on olemassa kokonaisluku x , jolloin ), mutta a ei ole jaollinen p :llä ; $x^{2}\equiv a{\pmod p}$
$\textstyle \left({\frac {a}{p}}\right)=-1$ , jos a on neliöllinen ei-jäännös mod p .

Ominaisuudet

Monimuotoisuus : . Multiplicatiivisuuden ilmeiset ominaisuudet ovat myös seuraavat: $\left({\frac {ab}{p}}\right)=\left({\frac {a}{p}}\right)\left({\frac {b}{p}}\ oikein)$
- jos ei jaollinen , niin $a$ $s$ $\left({\frac {a^{2}}{p}}\right)=1;$
- jos on kanoninen alkuluku, niin $a=p_{1}^{{\alpha _{1}}}\cdot p_{2}^{{\alpha _{2}}}\cdot \ldots \cdot p_{k}^{{\alpha _ {k}}}$ $a$ $\left({\frac {a}{p}}\right)=\left({\frac {p_{1}}{p}}\oikea)^{\alpha _{1}{\pmod {2}}}\cdot \left({\frac {p_{2}}{p}}\oikea)^{\alpha _{2}{\pmod {2}}}\cdot \ldots \cdot \left ({\frac {p_{k}}{p}}\oikea)^{\alpha _{k}{\pmod {2}}}.$
Jos , niin $a\equiv b{\pmod p}$ $\left({\frac {a}{p}}\right)=\left({\frac {b}{p}}\right).$
$\left({\frac {1}{p}}\right)=1.$
Gaussin lemma neliöllisistä jäännöksistä .
Eulerin kriteeri :

\left({\frac {a}{p}}\right)\equiv a^{(p-1)/2}{\pmod {p}}.

Jos , niin: $p\neq 2$

\left({\frac {-1}{p}}\right)=(-1)^{(p-1)/2}

(Euler-kriteerin erikoistapaus);

\left({\frac {2}{p}}\right)=(-1)^{(p^{2}-1)/8}.

Todiste

Jos ja on pariton, niin , ja parillinen ja päinvastoin. Siksi $x<{\frac {p}{2))$ $x$ $px>{\frac {p}{2))$ $px$

$1\cdot 2\cdot 3\cdot 4\cdot \ldots \cdot {\frac {p-1}{2}}=$

$=(-(-1))\cdot 2\cdot (-(-3))\cdot 4\cdot \ldots \cdot \left({\pm \left({\pm {\frac {p- 1}{2}}}\right)}\right)\equiv$

$\equiv (-{\väri {sininen}{(p-1))))\cdot {\väri {punainen}{2}}\cdot (-{\väri {sininen}{(p-3) }})\cdot {\väri {punainen}{4}}\cdot \ldots \cdot \left({\pm \left({\pm {\frac {p-1}{2}}}\right)} \right){\pmod {p}}\ ,$

jossa viimeisessä tulossa merkkien alla olevat luvut ovat parillisia ja kaikki parilliset luvut esiintyvät. Siten, merkitsee , meillä on $s={\frac {p-1}{2))$

$s!=1\cdot 2\cdot 3\cdot 4\cdot \ldots \cdot {\frac {p-1}{2}}\equiv$

$\equiv (-1)^{\lfloor {(s+1)/2}\rfloor }\cdot {\color {punainen}{2}}\cdot {\color {punainen}{4}}\ cdot \ldots \cdot {\väri {sininen}{(p-3)}}\cdot {\väri {sininen}{(p-1)))=(-1)^{\lfloor {(s+1) /2}\rfloor }\cdot 2^{s}(s!){\pmod {p}}$

Siksi , joka Eulerin kriteerin mukaan todistaa väitteen. $2^{s}\equiv (-1)^{\lfloor {(s+1)/2}\rfloor }=(-1)^{\frac {s(s+1)}{2} }=(-1)^{\frac {p^{2}-1}{8}}$

Kvadraattinen vastavuoroisuuden laki : Olkoot p ja q eriarvoisia parittomat alkuluvut, $\left({\frac {q}{p}}\right)=(-1)^{{\frac {p-1}{2}}\cdot {\frac {q-1}{2 ))}\cdot \left({\frac {p}{q}}\right).$
Jos , niin $p\equiv q{\pmod {4\cdot a))$

\left({\frac {a}{p}}\right)=\left({\frac {a}{q}}\right)

Kun , tasan puolet numeroista on Legendre-symboli yhtä suuri kuin 1, ja toisella puolella on symboli -1. $p\neq 2$ $1\leqslant a\leqslant p-1$

Kirjallisuus

Vinogradov I.M. Lukuteorian perusteet . - Moskova: GITTL, 1952. - P. 180. - ISBN 5-93972-252-0 .

Hahmot lukuteoriassa ja ryhmäteoriassa
Neliölliset merkit	Legendren symboli Jacobin symboli Kronecker-symboli - Jacobi
Tehojäämien merkit	Kuutiojäännöksen luonne Bikvadraattisen jäännöksen luonne Tehojäämän symboli