Символ Кронекера — Якоби — функция, используемая в теории чисел. Иногда называют символом Лежандра — Якоби — Кронекера или просто символом Кронекера.
Символ Кронекера — Якоби является обобщением символов Лежандра и Якоби. Символ Лежандра определён только для простых чисел, символ Якоби — для натуральных нечётных чисел, а символ Кронекера — Якоби расширяет это понятие на все целые числа.
Символ Кронекера — Якоби
определяется следующим образом:
- если
— простое нечётное число, то символ Кронекера — Якоби совпадает с символом Лежандра;
- если
, то ![{\displaystyle \left({\frac {a}{0}}\right)={\begin{cases}1,&{\text{if}}\ a=\pm 1,\\0,&{\text{if}}\ a\neq \pm 1;\end{cases}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/35c203aabace827f60295cfb7d5707d622c70344)
- если
, то ![{\displaystyle \left({\frac {a}{2}}\right)={\begin{cases}0,&{\text{if}}\ a\equiv 0{\pmod {2}},\\(-1)^{\frac {a^{2}-1}{8}},&{\text{if}}\ a\equiv 1{\pmod {2}};\end{cases}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/1727ba05b3b007a5f790904ee8939714a32601a2)
- если
, то ![{\displaystyle \left({\frac {a}{-1}}\right)={\begin{cases}-1,&{\text{if}}\ a<0,\\1,&{\text{if}}\ a\geqslant 0;\end{cases}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/5b08e3d47036218708c80fbf7658742e29c78fbd)
- если
, где
,
— простые (не обязательно различные), то
![{\displaystyle \left({\frac {a}{b}}\right)=\left({\frac {a}{\delta }}\right)\cdot \left({\frac {a}{p_{1}}}\right)\cdots \left({\frac {a}{p_{n}}}\right),}](https://wikimedia.org/api/rest_v1/media/math/render/svg/ddd292484e5303452712501d1ea30035121e913e)
где
определены выше.
тогда и только тогда, когда
(
и
не взаимно просты).
- Мультипликативность:
.
- В частности,
.
- Периодичность по переменной
: если
, то
- при
период равен
, то есть
;
- при
период равен
, то есть
.
- Периодичность по переменной
: если
, то
- при
период равен
, то есть
;
- при
период равен
, то есть
.
- Если
— нечётное натуральное число, то выполнены свойства символа Якоби:
![{\displaystyle \left({\frac {1}{b}}\right)=1;}](https://wikimedia.org/api/rest_v1/media/math/render/svg/5070e78fd01843126a9c427a67ad1a00cea24b12)
![{\displaystyle \left({\frac {-1}{b}}\right)=(-1)^{\frac {b-1}{2}};}](https://wikimedia.org/api/rest_v1/media/math/render/svg/ac2adf2505e2f70a5dc0bacfa3691d572f0f02f6)
![{\displaystyle \left({\frac {2}{b}}\right)=(-1)^{\frac {b^{2}-1}{8}}.}](https://wikimedia.org/api/rest_v1/media/math/render/svg/2a9ba624548f19829b0618ccaa97365e8efa59fc)
- Аналог квадратичного закона взаимности: если
— нечётные натуральные числа, то
.
Пусть
— натуральное число, а
взаимно просто с
.
Отображение
, действующее на всём
определяет перестановку
, чётность которой равна символу Якоби:
![{\displaystyle \sigma (\pi _{a})=\left({\frac {a}{n}}\right).}](https://wikimedia.org/api/rest_v1/media/math/render/svg/4a46ef2eba247b189d87fca631c680289aec06da)
1. (Случай b=0)
Если
то
Если
, то выход из алгоритма с ответом 1
Если
, то выход из алгоритма с ответом 0
Конец Если
2. (Чётность b)
Если a и b оба чётные, то выйти из алгоритма и вернуть 0
Цикл Пока b – чётное
Конец цикла
Если v – чётное, то k=1, иначе иначе
Если
, то
Если
, то
Конец Если
3. (Выход из алгоритма?)
Если
, то
Если
, то выход из алгоритма с ответом 0
Если
, то выход из алгоритма с ответом k
Конец Если
Цикл Пока a – чётное
Конец цикла
Если v – нечётное, то
4. (Применение квадратичного закона взаимности)
(наименьший положительный вычет)
Идти на шаг 3
Замечание: для подсчёта
не нужно вычислять показатель степени, достаточно знать остаток от деления
на 8. Это увеличивает скорость работы алгоритма.