Symbol Kronecker - Jacobi

Kronecker-Jacobiho symbol je funkce používaná v teorii čísel . Někdy označovaný jako symbol Legendre-Jacobi-Kronecker nebo jednoduše symbol Kronecker .

Symbol Kronecker-Jacobi je zobecněním Legendreho a Jacobiho symbolu . Legendreův symbol je definován pouze pro prvočísla, Jacobiho symbol je definován pro přirozená lichá čísla a Kronecker-Jacobiho symbol rozšiřuje tento koncept na všechna celá čísla.

Definice

Symbol Kronecker-Jacobi je definován takto: $\left(\frac{a}{b}\right)$

pokud je prvočíslo liché číslo, pak se symbol Kronecker-Jacobi shoduje se symbolem Legendre ; $b$
pokud , tak $b=0$ $\left({\frac {a}{0}}\right)={\begin{cases}1,&{\text{if}}\ a=\pm 1,\\0,&{\ text{if}}\ a\neq \pm 1;\end{cases}}$
pokud , tak $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))$
pokud , tak $b=-1$ $\left({\frac {a}{-1}}\right)={\begin{cases}-1,&{\text{if}}\ a<0,\\1,&{\ text{if}}\ a\geqslant 0;\end{cases}}$
jestliže , kde , jsou jednoduché (ne nutně odlišné), pak $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),

kde je definováno výše. $\left(\frac{a}{p_i}\right)$

Vlastnosti

$\left(\frac{a}{b}\right)=0$ pokud a pouze tehdy ( a nejsou coprime ). $(a,\;b)\neq 1$ $A$ $b$
Násobnost : . $\left(\frac{ab}{c}\right)=\left(\frac{a}{c}\right)\left(\frac{b}{c}\right)$
- Zejména . $\left(\frac{a^2b}{c}\right)=\left(\frac{b}{c}\right)$
Periodicita vzhledem k proměnné : if , then $A$ $b>0$
- když je období , to je ; $b\not \equiv 2{\pmod {4}}$ $b$ $\left(\frac{a+b}{b}\right)=\left(\frac{a}{b}\right)$
- když je období , to je . $b\equiv 2{\pmod {4}}$ $4b$ $\left(\frac{a+4b}{b}\right)=\left(\frac{a}{b}\right)$
Periodicita vzhledem k proměnné : if , then $b$ $a\neq 0$
- když je období , to je ; $a\equiv 0;\;1{\pmod {4}}$ $|a|$ $\left(\frac{a}{b+\left|a\right |}\right)=\left(\frac{a}{b}\right)$
- když je období , to je . $a\equiv 2;\;3{\pmod {4}}$ $4|a|$ $\left(\frac{a}{b+4\left|a\right |}\right)=\left(\frac{a}{b}\right)$
Pokud je liché přirozené číslo, pak vlastnosti Jacobiho symbolu platí: $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}}.$
Analogie kvadratického zákona reciprocity : jsou-li lichá přirozená čísla, pak . $A,\;B$ $\left(\frac{A}{B}\right)\left(\frac{B}{A}\right)=(-1)^{\frac{A-1}{2}\cdot\frac{ B-1}{2}}$

Spojení s permutacemi

Dovolit být přirozené číslo a coprime s . Mapování působící na vše definuje permutaci, jejíž parita je rovna Jacobiho symbolu: $n$ $A$ $n$ $m_a: x\to ax\mod n$ $\mathbb {Z} /n\mathbb {Z}$ $\pi_a\in S_n$

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

Algoritmus výpočtu

1. (Případ b=0 ) Pokud pak

b=0

Pokud , pak opusťte algoritmus s odpovědí 1

|a|=1

Pokud , pak opusťte algoritmus s odpovědí 0

|a|\neq1

End If 2. (I b ) Pokud jsou a i b sudé, ukončete algoritmus a vraťte 0

v=0

Zatímco smyčka b je sudá

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

Konec cyklu Je-li v sudé, pak k=1 , jinak

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

Pokud , pak

b<0

b:=-b

Pokud , pak

a<0

k:=-k

End If 3. (Opustit algoritmus?) Pokud , pak

a=0

Pokud , pak opusťte algoritmus s odpovědí 0

b>1

Pokud , pak výstup z algoritmu s odpovědí k

b=1

End If

v:=0

Smyčka, zatímco a je sudé

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

Konec cyklu Pokud je v liché, pak

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

4. (Aplikace kvadratického zákona reciprocity)

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

r:=|a|

a:=b\mod{r}

(nejméně kladný odpočet)

b:=r

Přejděte ke kroku 3

Poznámka: pro výpočet nemusíte počítat exponent, stačí znát zbytek dělení 8. Tím se zvýší rychlost algoritmu. $(-1)^{\frac{a^2-1}{8}}$ $A$

Reference

Vinogradov I.M. Základy teorie čísel . - Moskva: GITTL, 1952. - S. 180. - ISBN 5-93972-252-0 .
N. Cohen. Kurz výpočetní algebraické teorie čísel. - Springer, 1996. - ISBN 3-540-55640-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