Kronecker-symboli - Jacobi

Kronecker-Jacobi-symboli on lukuteoriassa käytetty funktio . Joskus kutsutaan Legendre-Jacobi-Kronecker- symboliksi tai yksinkertaisesti Kronecker-symboliksi .

Kronecker-Jacobi-symboli on yleistys Legendre- ja Jacobi -symboleista . Legendre-symboli on määritelty vain alkuluvuille, Jacobi- symboli on määritelty luonnollisille parittomille luvuille, ja Kronecker-Jacobi-symboli laajentaa tämän käsitteen kaikkiin kokonaislukuihin.

Määritelmä

Kronecker-Jacobi-symboli määritellään seuraavasti: $\left(\frac{a}{b}\right)$

jos on pariton alkuluku, niin Kronecker-Jacobi-symboli on sama kuin Legendre-symboli ; $b$
jos , niin $b = 0$ $\left({\frac {a}{0}}\right)={\begin{cases}1,&{\text{if}}\ a=\pm 1,\\0,&{\ teksti{if}}\ a\neq \pm 1;\end{cases}}$
jos , niin $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))$
jos , niin $b = -1$ $\left({\frac {a}{-1}}\right)={\begin{cases}-1,&{\text{if}}\ a<0,\\1,&{\ teksti{if}}\ a\geqslant 0;\end{cases}}$
jos , missä , ovat yksinkertaisia (ei välttämättä erillisiä), sitten $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 }}\oikea)\cdot \left({\frac {a}{p_ {1}}}\oikea)\cdots \left({\frac {a}{p_{n}}}\oikea),

missä edellä on määritelty. $\left(\frac{a}{p_i}\right)$

Ominaisuudet

$\left(\frac{a}{b}\right)=0$ jos ja vain jos ( ja eivät ole coprime ). $(a,\;b)\neq 1$ $a$ $b$
Monimuotoisuus : . $\left(\frac{ab}{c}\right)=\left(\frac{a}{c}\right)\left(\frac{b}{c}\right)$
- Erityisesti ,. $\left(\frac{a^2b}{c}\right)=\left(\frac{b}{c}\right)$
Jaksoisuus muuttujan suhteen : jos , niin $a$ $b>0$
- kun jakso on , eli ; $b\not \equiv 2{\pmod {4}}$ $b$ $\left(\frac{a+b}{b}\right)=\left(\frac{a}{b}\right)$
- kun aika on , eli . $b\equiv 2{\pmod {4}}$ $4b$ $\left(\frac{a+4b}{b}\right)=\left(\frac{a}{b}\right)$
Jaksoisuus muuttujan suhteen : jos , niin $b$ $a\neq 0$
- kun jakso on , eli ; $a\equiv 0;\;1{\pmod {4))$ $|a|$ $\left(\frac{a}{b+\left|a\right |}\right)=\left(\frac{a}{b}\right)$
- kun aika on , eli . $a\equiv 2;\;3{\pmod {4))$ $4|a|$ $\left(\frac{a}{b+4\left|a\right |}\right)=\left(\frac{a}{b}\right)$
Jos on pariton luonnollinen luku, niin Jacobi-symbolin ominaisuudet ovat voimassa: $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}}.$
Vastavuoroisuuden toisen asteen lain analogi : jos ovat parittomia luonnollisia lukuja, niin . $A,\;B$ $\left(\frac{A}{B}\right)\left(\frac{B}{A}\right)=(-1)^{\frac{A-1}{2}\cdot\frac{ B-1}{2}}$

Yhteys permutaatioilla

Antaa olla luonnollinen luku ja coprime kanssa . Kaikkeen vaikuttava kartoitus määrittelee permutaation , jonka pariteetti on sama kuin Jacobi-symboli: $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).

Laskenta-algoritmi

1. (Tapaus b=0 ) Jos sitten

b = 0

Jos , poistu algoritmista vastauksella 1

|a|=1

Jos , poistu algoritmista vastauksella 0

|a|\neq1

Loppu Jos 2. (Parillinen b ) Jos a ja b ovat molemmat parillisia, poistu algoritmista ja palauta 0

v=0

Kun silmukka b on parillinen

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

Jakson loppu Jos v on parillinen, niin k=1 , muuten

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

Jos , niin

b<0

b:=-b

Jos , niin

a<0

k:=-k

Loppu Jos 3. (Poistutko algoritmista?) Jos , niin

a = 0

Jos , poistu algoritmista vastauksella 0

b>1

Jos , niin poistuminen algoritmista vastauksella k

b = 1

Loppu Jos

v:=0

Silmukka kun a on parillinen

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

Jakson loppu Jos v on pariton, niin

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

4. (Kesävuoroisuuden toisen lain soveltaminen)

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

r:=|a|

a:=b\mod{r}

(vähiten positiivinen vähennys)

b:=r

Siirry vaiheeseen 3

Huomaa: laskentaa varten sinun ei tarvitse laskea eksponenttia, riittää, että tiedät jaon loppuosan 8:lla. Tämä lisää algoritmin nopeutta. $(-1)^{\frac{a^2-1}{8}}$ $a$

Viitteet

Vinogradov I.M. Lukuteorian perusteet . - Moskova: GITTL, 1952. - P. 180. - ISBN 5-93972-252-0 .
N. Cohen. Laskennallisen algebrallisen lukuteorian kurssi. - Springer, 1996. - ISBN 3-540-55640-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