Symbol för Legendre

Den aktuella versionen av sidan har ännu inte granskats av erfarna bidragsgivare och kan skilja sig väsentligt från versionen som granskades den 28 oktober 2021; verifiering kräver 1 redigering .

Legendre-symbolen är en funktion som används i talteorin . Introducerad av den franske matematikern A. M. Legendre . Legendre-symbolen är ett specialfall av Jacobi-symbolen , som i sin tur är ett specialfall av Kronecker-Jacobi-symbolen , ibland kallad Legendre-Jacobi-Kronecker-symbolen.

Definition

Låt a vara ett heltal och p ett annat primtal än 2. Legendre-symbolen definieras enligt följande: $\textstil \left({\frac {a}{p}}\right)$

$\textstil \left({\frac {a}{p}}\right)=0$ , om a är delbart med p ;
$\textstil \left({\frac {a}{p}}\right)=1$ , om a är en kvadratisk rest modulo p (det vill säga det finns ett heltal x så att ), men a är inte delbart med p ; $x^{2}\equiv a{\pmod p}$
$\textstil \left({\frac {a}{p}}\right)=-1$ , om a är en kvadratisk icke-rester mod p .

Egenskaper

Multipel : . De uppenbara egenskaperna hos multiplikativitet är också följande: $\left({\frac {ab}{p}}\right)=\left({\frac {a}{p}}\right)\left({\frac {b}{p}}\ höger)$
- om det inte är delbart med , då $a$ $sid$ $\left({\frac {a^{2}}{p}}\right)=1;$
- om är en kanonisk primtalsfaktorisering, alltså $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}}}.$
Om , då $a\equiv b{\pmod p}$ $\left({\frac {a}{p}}\right)=\left({\frac {b}{p}}\right).$
$\left({\frac {1}{p}}\right)=1.$
Gauss Lemma om kvadratiska rester .
Eulers kriterium :

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

Om , då: $p\neq 2$

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

(ett specialfall av Eulerkriteriet);

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

Bevis

Om och är udda, då , och jämnt, och vice versa. Det är därför $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 {blå}{(p-1))))\cdot {\color {röd}{2}}\cdot (-{\color {blå}{(p-3) }})\cdot {\color {röd}{4}}\cdot \ldots \cdot \left({\pm \left({\pm {\frac {p-1}{2}}}\right)} \right){\pmod {p}}\ ,$

där i den sista produkten är siffrorna under tecknen jämna, och alla jämna tal förekommer. Alltså, betecknande , har vi $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 {röd}{2}}\cdot {\color {röd}{4}}\ cdot \ldots \cdot {\color {blå}{(p-3)}}\cdot {\color {blå}{(p-1)))=(-1)^{\lgolv {(s+1) /2}\rgolv }\cdot 2^{s}(s!){\pmod {p}}$

Därför , vilket, genom Eulers kriterium, bevisar påståendet. $2^{s}\equiv (-1)^{\lfloor {(s+1)/2}\rfloor }=(-1)^{\frac {s(s+1)}{2} }=(-1)^{\frac {p^{2}-1}{8}}$

Kvadratisk lag för ömsesidighet : Låt p och q vara ojämna udda primtal då $\left({\frac {q}{p}}\right)=(-1)^{{\frac {p-1}{2}}\cdot {\frac {q-1}{2 ))}\cdot \left({\frac {p}{q}}\right).$
Om , då $p\equiv q{\pmod {4\cdot a))$

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

För exakt hälften av siffrorna har Legendre-symbolen lika med 1, och den andra hälften har symbolen lika med -1. $p\neq 2$ $1\leqslant a\leqslant p-1$

Litteratur

Vinogradov I.M. Grunderna i talteorin . - Moskva: GITTL, 1952. - S. 180. - ISBN 5-93972-252-0 .

Karaktärer i talteori och i gruppteori
Kvadratiska tecken	Symbol för Legendre Jacobi symbol Kronecker symbol - Jacobi
Karaktärer av kraftrester	Den kubiska återstodens natur Den biquadratiska restens natur Symbol för kraftrester