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

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

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

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

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

Пусть ${\displaystyle n}$ — натуральное число, а ${\displaystyle a}$ взаимно просто с ${\displaystyle n}$. Отображение ${\displaystyle m_{a}:x\to ax\mod n}$, действующее на всём ${\displaystyle \mathbb {Z} /n\mathbb {Z} }$ определяет перестановку ${\displaystyle \pi _{a}\in S_{n}}$, чётность которой равна символу Якоби:

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

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

 Если ${\displaystyle b=0}$ то

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

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

 Конец Если

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

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

 ${\displaystyle v=0}$

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

  ${\displaystyle v:=v+1;b:=b/2}$

 Конец цикла

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

 Если ${\displaystyle b<0}$, то

  ${\displaystyle b:=-b}$

  Если ${\displaystyle a<0}$, то ${\displaystyle k:=-k}$

 Конец Если

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

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

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

 Конец Если

 ${\displaystyle v:=0}$

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

  ${\displaystyle v:=v+1;a:=a/2}$

 Конец цикла

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

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

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

 ${\displaystyle r:=|a|}$

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

 ${\displaystyle b:=r}$

 Идти на шаг 3

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

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