Символ Кронекера — Якоби
— функция, используемая в
теории чисел
. Иногда называют
символом Лежандра — Якоби — Кронекера
или просто
символом Кронекера
.
Символ Кронекера — Якоби является обобщением
символов Лежандра
и
Якоби
.
Символ Лежандра
определён только для простых чисел,
символ Якоби
— для натуральных нечётных чисел, а символ Кронекера — Якоби расширяет это понятие на все целые числа.
Определение
Символ Кронекера — Якоби
определяется следующим образом:
-
если
— простое нечётное число, то символ Кронекера — Якоби совпадает с
символом Лежандра
;
-
если
, то
-
если
, то
-
если
, то
-
если
, где
,
— простые (не обязательно различные), то
-
где
определены выше.
Свойства
-
тогда и только тогда, когда
(
и
не
взаимно просты
).
-
Мультипликативность
:
.
-
В частности,
.
-
Периодичность
по переменной
: если
, то
-
при
период
равен
, то есть
;
-
при
период
равен
, то есть
.
-
Периодичность
по переменной
: если
, то
-
при
период
равен
, то есть
;
-
при
период
равен
, то есть
.
-
Если
— нечётное натуральное число, то выполнены свойства символа Якоби:
-
-
-
-
Аналог
квадратичного закона взаимности
: если
— нечётные натуральные числа, то
.
Связь с перестановками
Пусть
— натуральное число, а
взаимно просто с
.
Отображение
, действующее на всём
определяет перестановку
, чётность которой равна символу Якоби:
-
Алгоритм вычисления
1. (Случай b=0)
Если то
Если , то выход из алгоритма с ответом 1
Если , то выход из алгоритма с ответом 0
Конец Если
2. (Чётность b)
Если a и b оба чётные, то выйти из алгоритма и вернуть 0
Цикл Пока b – чётное
Конец цикла
Если v – чётное, то k=1, иначе иначе
Если , то
Если , то
Конец Если
3. (Выход из алгоритма?)
Если , то
Если , то выход из алгоритма с ответом 0
Если , то выход из алгоритма с ответом k
Конец Если
Цикл Пока a – чётное
Конец цикла
Если v – нечётное, то
4. (Применение квадратичного закона взаимности)
(наименьший положительный вычет)
Идти на шаг 3
Замечание:
для подсчёта
не нужно вычислять показатель степени, достаточно знать остаток от деления
на 8. Это увеличивает скорость работы алгоритма.
Список литературы