WikiSort.ru - Не сортированное

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

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

Определение

Символ Кронекера — Якоби ${\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.