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