Символ Кронекера — Якоби

Не следует путать с дельтой Кронекера.

Для термина «Кронекер» см. также другие значения.

Для термина «Якоби» см. также другие значения.

Символ Кронекера — Якоби — функция, используемая в теории чисел. Иногда называют символом Лежандра — Якоби — Кронекера или просто символом Кронекера.

Символ Кронекера — Якоби является обобщением символов Лежандра и Якоби. Символ Лежандра определён только для простых чисел, символ Якоби — для натуральных нечётных чисел, а символ Кронекера — Якоби расширяет это понятие на все целые числа.

Определение

Символ Кронекера — Якоби $\left({\frac {a}{b}}\right)$ определяется следующим образом:

• если $b$ — простое нечётное число, то символ Кронекера — Якоби совпадает с символом Лежандра;
• если $b=0$, то $\left({\frac {a}{0}}\right)={\begin{cases}1,&{\text{if}}\ a=\pm 1,\\0,&{\text{if}}\ a\neq \pm 1;\end{cases}}$
• если $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}}$
• если $b=-1$, то $\left({\frac {a}{-1}}\right)={\begin{cases}-1,&{\text{if}}\ a<0,\\1,&{\text{if}}\ a\geqslant 0;\end{cases}}$
• если $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),$

где $\left({\frac {a}{p_{i}}}\right)$ определены выше.

Свойства

• $\left({\frac {a}{b}}\right)=0$ тогда и только тогда, когда $(a,\;b)\neq 1$ ($a$ и $b$ не взаимно просты).
• Мультипликативность: $\left({\frac {ab}{c}}\right)=\left({\frac {a}{c}}\right)\left({\frac {b}{c}}\right)$.
  • В частности, $\left({\frac {a^{2}b}{c}}\right)=\left({\frac {b}{c}}\right)$.
• Периодичность по переменной $a$: если $b>0$, то
  • при $b\not \equiv 2{\pmod {4}}$ период равен $b$, то есть $\left({\frac {a+b}{b}}\right)=\left({\frac {a}{b}}\right)$;
  • при $b\equiv 2{\pmod {4}}$ период равен $4b$, то есть $\left({\frac {a+4b}{b}}\right)=\left({\frac {a}{b}}\right)$.
• Периодичность по переменной $b$: если $a\neq 0$, то
  • при $a\equiv 0;\;1{\pmod {4}}$ период равен $|a|$, то есть $\left({\frac {a}{b+\left|a\right|}}\right)=\left({\frac {a}{b}}\right)$;
  • при $a\equiv 2;\;3{\pmod {4}}$ период равен $4|a|$, то есть $\left({\frac {a}{b+4\left|a\right|}}\right)=\left({\frac {a}{b}}\right)$.
• Если $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,\;B$ — нечётные натуральные числа, то $\left({\frac {A}{B}}\right)\left({\frac {B}{A}}\right)=(-1)^{{\frac {A-1}{2}}\cdot {\frac {B-1}{2}}}$.

Связь с перестановками

Пусть $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).$

Алгоритм вычисления

1. (Случай b=0) 

 Если $b=0$ то

  Если $|a|=1$, то выход из алгоритма с ответом 1

  Если $|a|\neq 1$, то выход из алгоритма с ответом 0

 Конец Если

2. (Чётность b) 

 Если a и b оба чётные, то выйти из алгоритма и вернуть 0

 $v=0$

 Цикл Пока b – чётное

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

 Конец цикла

 Если v – чётное, то k=1, иначе иначе $k=(-1)^{\frac {a^{2}-1}{8}}$

 Если $b<0$, то

  $b:=-b$

  Если $a<0$, то $k:=-k$

 Конец Если

3. (Выход из алгоритма?)
 
 Если $a=0$, то

  Если $b>1$, то выход из алгоритма с ответом 0

  Если $b=1$, то выход из алгоритма с ответом k

 Конец Если

 $v:=0$

 Цикл Пока a – чётное

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

 Конец цикла

 Если v – нечётное, то $k:=(-1)^{\frac {b^{2}-1}{8}}k$

4. (Применение квадратичного закона взаимности)

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

 $r:=|a|$

 $a:=b\mod {r}$ (наименьший положительный вычет)

 $b:=r$

 Идти на шаг 3

Замечание: для подсчёта $(-1)^{\frac {a^{2}-1}{8}}$ не нужно вычислять показатель степени, достаточно знать остаток от деления $a$ на 8. Это увеличивает скорость работы алгоритма.

Список литературы

• Виноградов И. М. Основы теории чисел. — Москва: ГИТТЛ, 1952. — С. 180. — ISBN 5-93972-252-0.
• Н. Cohen. A course in computational algebraic number theory. — Springer, 1996. — ISBN 3-540-55640-0.