Kronecker szimbólum - Jacobi

A Kronecker-Jacobi szimbólum a számelméletben használt függvény . Néha Legendre-Jacobi-Kronecker szimbólumnak vagy egyszerűen Kronecker szimbólumnak nevezik .

A Kronecker-Jacobi szimbólum a Legendre és Jacobi szimbólumok általánosítása . A Legendre szimbólum csak prímszámokra, a Jacobi szimbólum a természetes páratlan számokra van definiálva, a Kronecker-Jacobi szimbólum pedig kiterjeszti ezt a fogalmat minden egész számra.

Definíció

A Kronecker-Jacobi szimbólum meghatározása a következő: $\left(\frac{a}{b}\right)$

ha páratlan prímszám, akkor a Kronecker-Jacobi szimbólum egybeesik a Legendre szimbólummal ; $b$
ha , akkor $b=0$ $\left({\frac {a}{0}}\right)={\begin{cases}1,&{\text{if}}\ a=\pm 1,\\0,&{\ szöveg{if}}\ a\neq \pm 1;\end{cases}}$
ha , akkor $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))$
ha , akkor $b=-1$ $\left({\frac {a}{-1}}\right)={\begin{cases}-1,&{\text{if}}\ a<0,\\1,&{\ szöveg{if}}\ a\geqslant 0;\end{cases}}$
ha , ahol , egyszerűek (nem feltétlenül különállóak), akkor $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}}}\jobbra)\cdots \left({\frac {a}{p_{n}}}\jobbra),

ahol fent meghatároztuk. $\left(\frac{a}{p_i}\right)$

Tulajdonságok

$\left(\frac{a}{b}\right)=0$ akkor és csak akkor, ha ( és nem koprím ). $(a,\;b)\neq 1$ $a$ $b$
Sokféleség : . $\left(\frac{ab}{c}\right)=\left(\frac{a}{c}\right)\left(\frac{b}{c}\right)$
- Különösen, . $\left(\frac{a^2b}{c}\right)=\left(\frac{b}{c}\right)$
Periodikus a változóra vonatkozóan : ha , akkor $a$ $b>0$
- amikor a periódus , azaz ; $b\not \equiv 2{\pmod {4}}$ $b$ $\left(\frac{a+b}{b}\right)=\left(\frac{a}{b}\right)$
- amikor az időszak , azaz . $b\equiv 2{\pmod {4}}$ $4b$ $\left(\frac{a+4b}{b}\right)=\left(\frac{a}{b}\right)$
Periodikus a változóra vonatkozóan : ha , akkor $b$ $a\neq 0$
- amikor a periódus , azaz ; $a\equiv 0;\;1{\pmod {4))$ $|a|$ $\left(\frac{a}{b+\left|a\right |}\right)=\left(\frac{a}{b}\right)$
- amikor az időszak , azaz . $a\equiv 2;\;3{\pmod {4))$ $4|a|$ $\left(\frac{a}{b+4\left|a\right |}\right)=\left(\frac{a}{b}\right)$
Ha páratlan természetes szám, akkor a Jacobi szimbólum tulajdonságai teljesülnek: $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}}.$
A reciprocitás másodfokú törvényének analógja : ha páratlan természetes számok vannak, akkor . $A,\;B$ $\left(\frac{A}{B}\right)\left(\frac{B}{A}\right)=(-1)^{\frac{A-1}{2}\cdot\frac{ B-1}{2}}$

Kapcsolódás permutációkkal

Legyen természetes szám, és egy prím -val . A mindenre ható leképezés egy permutációt határoz meg, amelynek paritása megegyezik a Jacobi szimbólummal: $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).

Számítási algoritmus

1. ( b=0 eset ) Ha akkor

b=0

Ha , akkor az 1-es válasszal lépjen ki az algoritmusból

|a|=1

Ha , akkor lépjen ki az algoritmusból 0 válasszal

|a|\neq1

Vége Ha 2. (Páros b ) Ha a és b páros, akkor lépjen ki az algoritmusból, és térjen vissza 0-val

v=0

Míg a b hurok páros

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

Ciklus vége Ha v páros, akkor k=1 , ellenkező esetben

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

Ha , akkor

b<0

b:=-b

Ha , akkor

a<0

k:=-k

Vége Ha 3. (Elhagyja az algoritmust?) Ha , akkor

a=0

Ha , akkor lépjen ki az algoritmusból 0 válasszal

b>1

Ha , akkor az algoritmusból való kilépés a k válasszal

b=1

Vége Ha

v:=0

Hurok, miközben a páros

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

Ciklus vége Ha v páratlan, akkor

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

4. (A reciprocitás másodfokú törvényének alkalmazása)

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

r:=|a|

a:=b\mod{r}

(legkevesebb pozitív levonás)

b:=r

Folytassák a 3. lépéssel

Megjegyzés: a számításhoz nem kell kitevőt számolni, elég tudni a 8-cal való osztás maradékát. Ez növeli az algoritmus sebességét. $(-1)^{\frac{a^2-1}{8}}$ $a$

Hivatkozások

Vinogradov I.M. A számelmélet alapjai . - Moszkva: GITTL, 1952. - P. 180. - ISBN 5-93972-252-0 .
N. Cohen. Számítási algebrai számelmélet tantárgy. - Springer, 1996. - ISBN 3-540-55640-0 .

Karakterek a számelméletben és a csoportelméletben
Másodfokú karakterek	A legenda szimbóluma Jacobi szimbólum Kronecker szimbólum - Jacobi
Az erőmaradékok karakterei	A köbös maradék természete A bikvadratikus maradék természete Teljesítmény maradék szimbólum