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

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

Определение


 Символ Кронекера — Якоби (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\{equiv1\{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. Это увеличивает скорость работы алгоритма.

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




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


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