Символ Кронекера — Якоби — Википедия

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

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

Определение

[править | править код]

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

  • если  — простое нечётное число, то символ Кронекера — Якоби совпадает с символом Лежандра;
  • если , то
  • если , то
  • если , то
  • если , где ,  — простые (не обязательно различные), то

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

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

Связь с перестановками

[править | править код]

Пусть — натуральное число, а взаимно просто с . Отображение , действующее на всём определяет перестановку , чётность которой равна символу Якоби:

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

[править | править код]
1. (Случай b=0)    Если  то    Если , то выход из алгоритма с ответом 1    Если , то выход из алгоритма с ответом 0   Конец Если  2. (Чётность b)    Если a и b оба чётные, то выйти из алгоритма и вернуть 0      Цикл Пока b – чётное       Конец цикла   Если v – чётное, то k=1, иначе иначе    Если , то        Если , то    Конец Если  3. (Выход из алгоритма?)    Если , то    Если , то выход из алгоритма с ответом 0    Если , то выход из алгоритма с ответом k   Конец Если      Цикл Пока a – чётное       Конец цикла   Если v – нечётное, то   4. (Применение квадратичного закона взаимности)          (наименьший положительный вычет)      Идти на шаг 3  

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

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

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