Символ Кронекера — Якоби

Не следует путать с дельтой Кронекера.
Для термина «Кронекер» см. также другие значения.
Для термина «Якоби» см. также другие значения.

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

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

ОпределениеПравить

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

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

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

СвойстваПравить

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

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

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

 

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

1. (Случай b=0) 

 Если   то

  Если  , то выход из алгоритма с ответом 1

  Если  , то выход из алгоритма с ответом 0

 Конец Если

2. (Чётность b) 

 Если a и b оба чётные, то выйти из алгоритма и вернуть 0

  

 Цикл Пока b – чётное

   

 Конец цикла

 Если v – чётное, то k=1, иначе иначе  

 Если  , то

   

  Если  , то  

 Конец Если

3. (Выход из алгоритма?)
 
 Если  , то

  Если  , то выход из алгоритма с ответом 0

  Если  , то выход из алгоритма с ответом k

 Конец Если

  

 Цикл Пока a – чётное

   

 Конец цикла

 Если v – нечётное, то  

4. (Применение квадратичного закона взаимности)

  

  

   (наименьший положительный вычет)

  

 Идти на шаг 3

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

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