Symbol Legendre

Aktuální verze stránky ještě nebyla zkontrolována zkušenými přispěvateli a může se výrazně lišit od verze recenzované 28. října 2021; ověření vyžaduje 1 úpravu .

Legendreův symbol je funkce používaná v teorii čísel . Zavedl francouzský matematik A. M. Legendre . Legendreův symbol je speciální případ Jacobiho symbolu , což je zase zvláštní případ Kronecker-Jacobiho symbolu , někdy nazývaného Legendre-Jacobi-Kroneckerův symbol.

Definice

Nechť a je celé číslo a p je prvočíslo jiné než 2. Legendreův symbol je definován následovně: $\textstyle \left({\frac {a}{p}}\right)$

$\textstyle \left({\frac {a}{p}}\right)=0$ , je-li a dělitelné p ;
$\textstyle \left({\frac {a}{p}}\right)=1$ , jestliže a je kvadratický zbytek modulo p (to znamená, že existuje celé číslo x takové, že ), ale a není dělitelné p ; $x^{2}\equiv a{\pmod p}$
$\textstyle \left({\frac {a}{p}}\right)=-1$ , je-li a kvadratický nezbytkový mod p .

Vlastnosti

Násobnost : . Zjevné vlastnosti multiplikativnosti jsou také následující: $\left({\frac {ab}{p}}\right)=\left({\frac {a}{p}}\right)\left({\frac {b}{p}}\ že jo)$
- není -li dělitelné , pak $A$ $p$ $\left({\frac {a^{2}}{p}}\right)=1;$
- pokud je kanonická prvočíselná faktorizace, pak $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}}\right)^{\alpha _{1}{\pmod {2}}}\cdot \left({\frac {p_{2}}{p}}\right)^{\alpha _{2}{\pmod {2}}}\cdot \ldots \cdot \left ({\frac {p_{k}}{p}}\right)^{\alpha _{k}{\pmod {2}}}.$
Pokud , pak $a\equiv b{\pmod p}$ $\left({\frac {a}{p}}\right)=\left({\frac {b}{p}}\right).$
$\left({\frac {1}{p}}\right)=1.$
Gaussovo lemma o kvadratických zbytcích .
Eulerovo kritérium :

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

Pokud , pak: $p\neq 2$

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

(zvláštní případ Eulerova kritéria);

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

Důkaz

Jestliže a je liché, pak , a sudé a naopak. Proto $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 (-{\color {blue}{(p-1))))\cdot {\color {red}{2}}\cdot (-{\color {blue}{(p-3) }})\cdot {\color {červená}{4}}\cdot \ldots \cdot \left({\pm \left({\pm {\frac {p-1}{2}}}\right)} \right){\pmod {p}}\ ,$

kde v posledním součinu jsou čísla pod znaménky sudá a všechna sudá čísla se vyskytují. Tak, označující , máme $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 {červená}{2}}\cdot {\color {červená}{4}}\ cdot \ldots \cdot {\color {modrá}{(p-3)}}\cdot {\barva {modrá}{(p-1)))=(-1)^{\lpatro {(s+1) /2}\rpodlaží }\cdot 2^{s}(y!){\pmod {p}}$

Tedy , což podle Eulerova kritéria dokazuje tvrzení. $2^{s}\equiv (-1)^{\lpatro {(s+1)/2}\rfloor }=(-1)^{\frac {s(s+1)}{2} }=(-1)^{\frac {p^{2}-1}{8}}$

Kvadratický zákon reciprocity : Nechť p a q jsou nestejná lichá prvočísla $\left({\frac {q}{p}}\right)=(-1)^{{\frac {p-1}{2}}\cdot {\frac {q-1}{2 ))}\cdot \left({\frac {p}{q}}\right).$
Pokud , pak $p\equiv q{\pmod {4\cdot a))$

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

Pro přesně polovina čísel má Legendreův symbol rovný 1 a druhá polovina má symbol rovný -1. $p\neq 2$ $1\leqslant a\leqslant p-1$

Literatura

Vinogradov I.M. Základy teorie čísel . - Moskva: GITTL, 1952. - S. 180. - ISBN 5-93972-252-0 .

Znaky v teorii čísel a v teorii grup
Kvadratické znaky	Symbol Legendre Jacobiho symbol Symbol Kronecker - Jacobi
Postavy zbytků moci	Povaha krychlového zbytku Povaha bikvadratického zbytku Symbol zbytku energie