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

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

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

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

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

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

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

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

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

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

 

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

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.