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

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

Определение


 Символ Кронекера — Якоби (ab) определяется следующим образом:

  • если b — простое нечётное число, то символ Кронекера — Якоби совпадает с символом Лежандра;
  • если b=0, то \{left(\{frac\{a\}\{0\}\{right)=

 \{begin\{cases\}
 \texttt1, \& \{text\{if\}\{ a=\{pm 1, \{\{\\\texttt0, \& \{text\{if\}\{ a\{neq\{pm 1;
 \{end\{cases\}

  • если b=2, то \{left(\{frac\{a\}\{2\}\{right)=

 \{begin\{cases\}
 \texttt0, \& \{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 \textless 0, \{\{ 1, \& \{text\{if\}\{ a\{geqslant 0; \{end\{cases\}

  • если b=δp1pn, где δ=±1, p1,,pn — простые (не обязательно различные), то


(ab)=(aδ)(ap1)(apn),
  где (api) определены выше.

Свойства



  • (ab)=0 тогда и только тогда, когда (a,b)1 (a и b не взаимно просты).
  • Мультипликативность: (abc)=(ac)(bc).
    • В частности, (a2bc)=(bc).

  • Периодичность по переменной a: если b>0, то
    • при b2(mod4) период равен b, то есть (a+bb)=(ab);
    • при b2(mod4) период равен 4b, то есть (a+4bb)=(ab).

  • Периодичность по переменной b: если a0, то
    • при a0;1(mod4) период равен |a|, то есть (ab+|a|)=(ab);
    • при a2;3(mod4) период равен 4|a|, то есть (ab+4|a|)=(ab).

  • Если b — нечётное натуральное число, то выполнены свойства символа Якоби:
    • (1b)=1;
    • (1b)=(1)b12
    • (2b)=(1)b218.

  • Аналог квадратичного закона взаимности: если A,B — нечётные натуральные числа, то (AB)(BA)=(1)A12B12.

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


 Пусть n — натуральное число, а a взаимно просто с n. Отображение ma:xaxmodn, действующее на всём Z/nZ определяет перестановку πaSn, чётность которой равна символу Якоби:
σ(πa)=(an).

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


\texttt1. \texttt(Случай \textttb=0\texttt)\texttt \\\\\texttt Если b=0\texttt то\\\\\texttt  Если |a|=1\texttt, то выход из алгоритма с ответом 1\\\\\texttt  Если |a|1\texttt, то выход из алгоритма с ответом 0\\\\\texttt Конец Если\\\\\texttt2. \texttt(Чётность \textttb\texttt)\texttt \\\\\texttt Если \texttta\texttt и \textttb\texttt оба чётные, то выйти из алгоритма и вернуть 0\\\\\texttt v=0\\\\\texttt Цикл Пока \textttb\texttt – чётное\\\\\texttt  v:=v+1;b:=b/2\\\\\texttt Конец цикла\\\\\texttt Если \textttv\texttt – чётное, то \textttk=1\texttt, иначе иначе k=(1)a218\\\\\texttt Если b<0\texttt, то\\\\\texttt  b:=b\\\\\texttt  Если a<0\texttt, то k:=k\\\\\texttt Конец Если\\\\\texttt3. \texttt(Выход \textttиз \textttалгоритма?)\\\texttt \\\texttt Если a=0\texttt, то\\\\\texttt  Если b>1\texttt, то выход из алгоритма с ответом 0\\\\\texttt  Если b=1\texttt, то выход из алгоритма с ответом \textttk\\\\\texttt Конец Если\\\\\texttt v:=0\\\\\texttt Цикл Пока \texttta\texttt – чётное\\\\\texttt  v:=v+1;a:=a/2\\\\\texttt Конец цикла\\\\\texttt Если \textttv\texttt – нечётное, то k:=(1)b218k\\\\\texttt4. \texttt(Применение \textttквадратичного \textttзакона \textttвзаимности)\\\\\texttt k:=k(1)(a1)(b1)4\\\\\texttt r:=|a|\\\\\texttt a:=bmodr\texttt (наименьший положительный вычет)\\\\\texttt b:=r\\\\\texttt Идти на шаг 3\\
Замечание: для подсчёта (1)a218 не нужно вычислять показатель степени, достаточно знать остаток от деления a на 8. Это увеличивает скорость работы алгоритма.

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




 заглавие=Основы теории чисел ссылка= http://www.mccme.ru/free-books/djvu/vinogradov.djvu автор= Виноградов И. М. год=1952 место=Москва издательство= ГИТТЛ страницы=180 isbn=5-93972-252-0 \}\}


 подзаголовок заглавие=A course in computational algebraic number theory оригинал= ссылка= автор= Н. Cohen год=1996 место= издательство=Springer страницы= isbn= 3-540-55640-0 \}\}
 Категория:Теория чисел