Символ Кронекера — Якоби — функция, используемая в теории чисел . Иногда называют символом Лежандра — Якоби — Кронекера или просто символом Кронекера .
Символ Кронекера — Якоби является обобщением символов Лежандра и Якоби . Символ Лежандра определён только для простых чисел, символ Якоби — для натуральных нечётных чисел, а символ Кронекера — Якоби расширяет это понятие на все целые числа.
Символ Кронекера — Якоби
(
a
b
)
{\displaystyle \left({\frac {a}{b}}\right)}
если
b
{\displaystyle b}
символом Лежандра ;
если
b
=
0
{\displaystyle b=0}
(
a
0
)
=
{
1
,
if
a
=
±
1
,
0
,
if
a
≠
±
1
;
{\displaystyle \left({\frac {a}{0}}\right)={\begin{cases}1,&{\text{if}}\ a=\pm 1,\\0,&{\text{if}}\ a\neq \pm 1;\end{cases}}}
если
b
=
2
{\displaystyle b=2}
(
a
2
)
=
{
0
,
if
a
≡
0
(
mod
2
)
,
(
−
1
)
a
2
−
1
8
,
if
a
≡
1
(
mod
2
)
;
{\displaystyle \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}}}
если
b
=
−
1
{\displaystyle b=-1}
(
a
−
1
)
=
{
−
1
,
if
a
<
0
,
1
,
if
a
⩾
0
;
{\displaystyle \left({\frac {a}{-1}}\right)={\begin{cases}-1,&{\text{if}}\ a<0,\\1,&{\text{if}}\ a\geqslant 0;\end{cases}}}
если
b
=
δ
⋅
p
1
⋅
…
⋅
p
n
{\displaystyle b=\delta \cdot p_{1}\cdot \ldots \cdot p_{n}}
δ
=
±
1
{\displaystyle \delta =\pm 1}
p
1
,
…
,
p
n
{\displaystyle p_{1},\;\ldots ,\;p_{n}}
(
a
b
)
=
(
a
δ
)
⋅
(
a
p
1
)
⋯
(
a
p
n
)
,
{\displaystyle \left({\frac {a}{b}}\right)=\left({\frac {a}{\delta }}\right)\cdot \left({\frac {a}{p_{1}}}\right)\cdots \left({\frac {a}{p_{n}}}\right),}
где
(
a
p
i
)
{\displaystyle \left({\frac {a}{p_{i}}}\right)}
(
a
b
)
=
0
{\displaystyle \left({\frac {a}{b}}\right)=0}
(
a
,
b
)
≠
1
{\displaystyle (a,\;b)\neq 1}
a
{\displaystyle a}
b
{\displaystyle b}
взаимно просты ).Мультипликативность :
(
a
b
c
)
=
(
a
c
)
(
b
c
)
{\displaystyle \left({\frac {ab}{c}}\right)=\left({\frac {a}{c}}\right)\left({\frac {b}{c}}\right)}
В частности,
(
a
2
b
c
)
=
(
b
c
)
{\displaystyle \left({\frac {a^{2}b}{c}}\right)=\left({\frac {b}{c}}\right)}
Периодичность по переменной
a
{\displaystyle a}
b
>
0
{\displaystyle b>0}
при
b
≢
2
(
mod
4
)
{\displaystyle b\not \equiv 2{\pmod {4}}}
период равен
b
{\displaystyle b}
(
a
+
b
b
)
=
(
a
b
)
{\displaystyle \left({\frac {a+b}{b}}\right)=\left({\frac {a}{b}}\right)}
при
b
≡
2
(
mod
4
)
{\displaystyle b\equiv 2{\pmod {4}}}
период равен
4
b
{\displaystyle 4b}
(
a
+
4
b
b
)
=
(
a
b
)
{\displaystyle \left({\frac {a+4b}{b}}\right)=\left({\frac {a}{b}}\right)}
Периодичность по переменной
b
{\displaystyle b}
a
≠
0
{\displaystyle a\neq 0}
при
a
≡
0
;
1
(
mod
4
)
{\displaystyle a\equiv 0;\;1{\pmod {4}}}
период равен
|
a
|
{\displaystyle |a|}
(
a
b
+
|
a
|
)
=
(
a
b
)
{\displaystyle \left({\frac {a}{b+\left|a\right|}}\right)=\left({\frac {a}{b}}\right)}
при
a
≡
2
;
3
(
mod
4
)
{\displaystyle a\equiv 2;\;3{\pmod {4}}}
период равен
4
|
a
|
{\displaystyle 4|a|}
(
a
b
+
4
|
a
|
)
=
(
a
b
)
{\displaystyle \left({\frac {a}{b+4\left|a\right|}}\right)=\left({\frac {a}{b}}\right)}
Если
b
{\displaystyle b}
(
1
b
)
=
1
;
{\displaystyle \left({\frac {1}{b}}\right)=1;}
(
−
1
b
)
=
(
−
1
)
b
−
1
2
;
{\displaystyle \left({\frac {-1}{b}}\right)=(-1)^{\frac {b-1}{2}};}
(
2
b
)
=
(
−
1
)
b
2
−
1
8
.
{\displaystyle \left({\frac {2}{b}}\right)=(-1)^{\frac {b^{2}-1}{8}}.}
Аналог квадратичного закона взаимности : если
A
,
B
{\displaystyle A,\;B}
(
A
B
)
(
B
A
)
=
(
−
1
)
A
−
1
2
⋅
B
−
1
2
{\displaystyle \left({\frac {A}{B}}\right)\left({\frac {B}{A}}\right)=(-1)^{{\frac {A-1}{2}}\cdot {\frac {B-1}{2}}}}
Пусть
n
{\displaystyle n}
a
{\displaystyle a}
n
{\displaystyle n}
m
a
:
x
→
a
x
mod
n
{\displaystyle m_{a}:x\to ax\mod n}
Z
/
n
Z
{\displaystyle \mathbb {Z} /n\mathbb {Z} }
π
a
∈
S
n
{\displaystyle \pi _{a}\in S_{n}}
σ
(
π
a
)
=
(
a
n
)
.
{\displaystyle \sigma (\pi _{a})=\left({\frac {a}{n}}\right).}
1. (Случай b=0 )
Если
b
=
0
{\displaystyle b=0}
|
a
|
=
1
{\displaystyle |a|=1}
|
a
|
≠
1
{\displaystyle |a|\neq 1}
2. (Чётность b )
Если a и b оба чётные, то выйти из алгоритма и вернуть 0
v
=
0
{\displaystyle v=0}
b – чётное
v
:=
v
+
1
;
b
:=
b
/
2
{\displaystyle v:=v+1;b:=b/2}
v – чётное, то k=1 , иначе иначе
k
=
(
−
1
)
a
2
−
1
8
{\displaystyle k=(-1)^{\frac {a^{2}-1}{8}}}
b
<
0
{\displaystyle b<0}
b
:=
−
b
{\displaystyle b:=-b}
a
<
0
{\displaystyle a<0}
k
:=
−
k
{\displaystyle k:=-k}
3. (Выход из алгоритма?)
Если
a
=
0
{\displaystyle a=0}
b
>
1
{\displaystyle b>1}
b
=
1
{\displaystyle b=1}
k
Конец Если
v
:=
0
{\displaystyle v:=0}
a – чётное
v
:=
v
+
1
;
a
:=
a
/
2
{\displaystyle v:=v+1;a:=a/2}
v – нечётное, то
k
:=
(
−
1
)
b
2
−
1
8
k
{\displaystyle k:=(-1)^{\frac {b^{2}-1}{8}}k}
4. (Применение квадратичного закона взаимности)
k
:=
k
(
−
1
)
(
a
−
1
)
(
b
−
1
)
4
{\displaystyle k:=k(-1)^{\frac {(a-1)(b-1)}{4}}}
r
:=
|
a
|
{\displaystyle r:=|a|}
a
:=
b
mod
r
{\displaystyle a:=b\mod {r}}
b
:=
r
{\displaystyle b:=r}
Замечание: для подсчёта
(
−
1
)
a
2
−
1
8
{\displaystyle (-1)^{\frac {a^{2}-1}{8}}}
a
{\displaystyle a}
