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