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

Не следует путать с дельтой Кронекера.

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

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

Определение

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

если — простое нечётное число, то символ Кронекера — Якоби совпадает с символом Лежандра;
если , то $\left(\frac{a}{0}\right)= \begin{cases} 1 & \Leftrightarrow a=\pm 1, \\ 0 & \Leftrightarrow a\neq\pm 1; \end{cases}$
если , то $\left(\frac{a}{2}\right)= \begin{cases} 0 & \Leftrightarrow a\equiv 0\mod 2, \\ (-1)^{\frac{a^2-1}{8}} & \Leftrightarrow a\equiv 1\mod 2; \end{cases}$
если , то $\left(\frac{a}{-1}\right)= \begin{cases} -1 & \Leftrightarrow a < 0, \\ 1 & \Leftrightarrow a\geqslant 0; \end{cases}$
если , где , — простые (не обязательно различные), то

где — определены выше.

Свойства

тогда и только тогда, когда ( и не взаимно просты).
Мультипликативность: .
- В частности, .
Периодичность по переменной : если , то
- при период равен , то есть ;
- при период равен , то есть .
Периодичность по переменной : если , то
- при период равен , то есть ;
- при период равен , то есть .
Если — нечётное натуральное число, то выполнены свойства символа Якоби:
Аналог квадратичного закона взаимности: если — нечётные натуральные числа, то .

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

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

 Если  то

  Если , то выход из алгоритма с ответом 1

  Если , то выход из алгоритма с ответом 0

 Конец Если

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

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

 

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

  

 Конец цикла

 Если v – чётное, то k=1, иначе иначе 

 Если , то

  

  Если , то 

 Конец Если

3. (Выход из алгоритма?)
 
 Если , то

  Если , то выход из алгоритма с ответом 0

  Если , то выход из алгоритма с ответом k

 Конец Если

 

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

  

 Конец цикла

 Если v – нечётное, то 

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

 

 

  (наименьший положительный вычет)

 

 Идти на шаг 3

Замечание: для подсчёта не нужно вычислять показатель степени, достаточно знать остаток от деления на 8. Это увеличивает скорость работы алгоритма.

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

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

Характеры в теории чисел и Характер в теории групп
Квадратичные характеры	Символ Лежандра • Символ Якоби • Символ Кронекера — Якоби
Характеры степенных вычетов	Характер кубического вычета • Характер биквадратичного вычета • Символ степенного вычета

Selhoz-katalog.ru

Сельхоз каталог

Обзоры