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

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

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

Определение

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

• если $b$ — простое нечётное число, то символ Кронекера — Якоби совпадает с символом Лежандра;
• если $b=0$, то $\left(\frac{a}{0}\right)=\{\begin{array}{cc}1,& \text{if}a=\pm 1,\\ 0,& \text{if}a\ne \pm 1;\end{array}$
• если $b=2$, то $\left(\frac{a}{2}\right)=\{\begin{array}{cc}0,& \text{if}a\equiv 0(\mathrm{mod}2),\\ (-1{)}^{\frac{a^2-1}{8}},& \text{if}a\equiv 1(\mathrm{mod}2);\end{array}$
• если $b=-1$, то $\left(\frac{a}{-1}\right)=\{\begin{array}{cc}-1,& \text{if}a<0,\\ 1,& \text{if}a⩾0;\end{array}$
• если $b=\delta \cdot p_1\cdot \dots \cdot p_n$, где $\delta =\pm 1$, $p_1,\dots ,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)\ne 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\equiv ̸2(\mathrm{mod}4)$ период равен $b$, то есть $\left(\frac{a+b}{b}\right)=\left(\frac{a}{b}\right)$;
  • при $b\equiv 2(\mathrm{mod}4)$ период равен $4b$, то есть $\left(\frac{a+4b}{b}\right)=\left(\frac{a}{b}\right)$.
• Периодичность по переменной $b$: если $a\ne 0$, то
  • при $a\equiv 0;1(\mathrm{mod}4)$ период равен $|a|$, то есть $\left(\frac{a}{b+\left|a\right|}\right)=\left(\frac{a}{b}\right)$;
  • при $a\equiv 2;3(\mathrm{mod}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 axmodn$, действующее на всём $\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|\ne 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:=bmodr$ (наименьший положительный вычет)

 $b:=r$

 Идти на шаг 3

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

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

• Шаблон:Книга
• Шаблон:Книга