Kronecker symbol - Jacobi

Kronecker-Jacobi symbolet er en funktion, der bruges i talteorien . Nogle gange omtalt som Legendre-Jacobi-Kronecker- symbolet eller blot Kronecker-symbolet .

Kronecker-Jacobi-symbolet er en generalisering af Legendre- og Jacobi -symbolerne . Legendre-symbolet er kun defineret for primtal, Jacobi -symbolet er defineret for naturlige ulige tal, og Kronecker-Jacobi-symbolet udvider dette koncept til alle heltal.

Definition

Kronecker-Jacobi symbolet er defineret som følger: $\left(\frac{a}{b}\right)$

hvis er et ulige primtal, så falder Kronecker-Jacobi-symbolet sammen med Legendre-symbolet ; $b$
hvis , så $b=0$ $\left({\frac {a}{0}}\right)={\begin{cases}1,&{\text{if}}\ a=\pm 1,\\0,&{\ tekst{if}}\ a\neq \pm 1;\end{cases}}$
hvis , så $b=2$ $\left({\frac {a}{2}}\right)={\begin{cases}0,&{\text{if}}\ a\equiv 0{\pmod {2}},\ \(-1)^{\frac {a^{2}-1}{8)),&{\text{if))\ a\equiv 1{\pmod {2));\end{cases))$
hvis , så $b=-1$ $\left({\frac {a}{-1}}\right)={\begin{cases}-1,&{\text{if}}\ a<0,\\1,&{\ tekst{if}}\ a\geqslant 0;\end{cases}}$
hvis , hvor , er enkle (ikke nødvendigvis forskellige), så $b=\delta\cdot p_1\cdot\ldots\cdot p_n$ $\delta=\pm 1$ $p_{1},\;\ldots ,\;p_{n}$

\left({\frac {a}{b}}\right)=\left({\frac {a}{\delta }}\right)\cdot \left({\frac {a}{p_ {1}}}\right)\cdots \left({\frac {a}{p_{n}}}\right),

hvor det er defineret ovenfor. $\left(\frac{a}{p_i}\right)$

Egenskaber

$\left(\frac{a}{b}\right)=0$ hvis og kun hvis ( og ikke er coprime ). $(a,\;b)\neq 1$ $-en$ $b$
Multiplikitet :. _ $\left(\frac{ab}{c}\right)=\left(\frac{a}{c}\right)\left(\frac{b}{c}\right)$
- Især . $\left(\frac{a^2b}{c}\right)=\left(\frac{b}{c}\right)$
Periodicitet med hensyn til variablen : hvis , så $-en$ $b>0$
- når perioden er , dvs. $b\not \equiv 2{\pmod {4}}$ $b$ $\left(\frac{a+b}{b}\right)=\left(\frac{a}{b}\right)$
- når perioden er , dvs. $b\equiv 2{\pmod {4}}$ $4b$ $\left(\frac{a+4b}{b}\right)=\left(\frac{a}{b}\right)$
Periodicitet med hensyn til variablen : hvis , så $b$ $a\neq 0$
- når perioden er , dvs. $a\equiv 0;\;1{\pmod {4}}$ $|a|$ $\left(\frac{a}{b+\left|a\right |}\right)=\left(\frac{a}{b}\right)$
- når perioden er , dvs. $a\equiv 2;\;3{\pmod {4}}$ $4|a|$ $\left(\frac{a}{b+4\left|a\right |}\right)=\left(\frac{a}{b}\right)$
Hvis er et ulige naturligt tal, så gælder egenskaberne for Jacobi-symbolet: $b$
- $\left(\frac{1}{b}\right)=1;$
- $\left(\frac{-1}{b}\right)=(-1)^{\frac{b-1}{2}});$
- $\left(\frac{2}{b}\right)=(-1)^{\frac{b^2-1}{8}}.$
En analog af den kvadratiske lov om gensidighed : hvis er ulige naturlige tal, så . $A,\;B$ $\left(\frac{A}{B}\right)\left(\frac{B}{A}\right)=(-1)^{\frac{A-1}{2}\cdot\frac{ B-1}{2}}$

Forbindelse med permutationer

Lade være et naturligt tal og coprime med . Kortlægningen , der virker på alt, definerer en permutation , hvis paritet er lig med Jacobi-symbolet: $n$ $-en$ $n$ $m_a: x\til ax\mod n$ $\mathbb {Z} /n\mathbb {Z}$ $\pi_a\i S_n$

\sigma (\pi _{a})=\left({\frac {a}{n}}\right).

Beregningsalgoritme

1. (Case b=0 ) Hvis da

b=0

Hvis , så forlad algoritmen med svar 1

|a|=1

Hvis , så forlad algoritmen med svaret 0

|a|\neq1

Afslut Hvis 2. (Selv b ) Hvis a og b begge er lige, så forlad algoritmen og returner 0

v=0

Mens sløjfe b er lige

v:=v+1; b:=b/2

Slut på cyklus Hvis v er lige, så er k=1 , ellers

k=(-1)^{\frac{a^2-1}{8}}

Hvis , så

b<0

b:=-b

Hvis , så

a<0

k:=-k

Afslut Hvis 3. (Forlader du algoritmen?) Hvis , så

a=0

Hvis , så forlad algoritmen med svaret 0

b>1

Hvis , så udgangen fra algoritmen med svaret k

b=1

Afslut Hvis

v:=0

Loop mens a er lige

v:=v+1; a:=a/2

Slut på cyklus Hvis v er ulige, så

k:=(-1)^{\frac{b^2-1}{8}}k

4. (Anvendelse af den kvadratiske lov om gensidighed)

k:=k(-1) ^{\frac{(a-1)(b-1)}{4))

r:=|a|

a:=b\mod{r}

(mindst positive fradrag)

b:=r

Gå til trin 3

Bemærk: til beregningen behøver du ikke at beregne eksponenten, det er nok at kende resten af divisionen med 8. Dette øger algoritmens hastighed. $(-1)^{\frac{a^2-1}{8}}$ $-en$

Referencer

Vinogradov I.M. Grundlæggende om talteori . - Moskva: GITTL, 1952. - S. 180. - ISBN 5-93972-252-0 .
N. Cohen. Et kursus i beregningsmæssig algebraisk talteori. - Springer, 1996. - ISBN 3-540-55640-0 .

Karakterer i talteori og i gruppeteori
Kvadratiske tegn	Symbol for Legendre Jacobi symbol Kronecker symbol - Jacobi
Karakterer af kraftrester	Arten af den kubiske rest Naturen af den biquadratiske rest Symbol for strømrester