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

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

Не следует путать с Символ Кронекера.

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

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

Определение

Символ Кронекера-Якоби $\left(\frac{a}{b}\right)$ определяется следующим образом:

• если b — простое нечётное число, то символ Кронекера-Якоби совпадает с символом Лежандра

• если b=0, то $\left(\frac{a}{0}\right)= \begin{cases} 1 & \Leftrightarrow a=\pm1\\ 0 & \Leftrightarrow a\neq\pm1 \end{cases}$

• если b=2, то $\left(\frac{a}{2}\right) = \begin{cases} 0 & \Leftrightarrow a\equiv0\mod{2}\\ (-1)^{\frac{a^2-1}{8}} & \Leftrightarrow a\equiv1\mod{2} \end{cases}$

• если b=-1, то $\left(\frac{a}{-1}\right) = \begin{cases} -1 & \Leftrightarrow a < 0 \\ 1 & \Leftrightarrow a\geq 0 \end{cases}$

• если $b=\delta\cdot p_1\cdot ...\cdot p_n$, где $\delta=\pm1$, p₁,...,p_n — простые (не обязательно различные), то

$\left(\frac{a}{b}\right) = \left(\frac{a}{\delta}\right)\cdot\left(\frac{a}{p_1}\right)\cdot...\cdot\left(\frac{a}{p_n}\right),$

где $\left(\frac{a}{p_i}\right)$ — определены выше.

Свойства

• $\left(\frac{a}{b}\right)=0$ тогда и только тогда, когда $(a,b)\neq1$ (a и b не взаимно просты)

• Мультипликативность: $\left(\frac{ab}{c}\right) = \left(\frac{a}{c}\right) \left(\frac{b}{c}\right)$

• • В частности, $\left(\frac{a^2b}{c}\right) =\left(\frac{b}{c}\right)$

• Периодичность по переменной a: если b > 0, то

• • при $b\not\equiv2\mod{4}$ период равен b, то есть $\left(\frac{a+b}{b}\right)= \left(\frac{a}{b}\right)$

• • при $b \equiv2\mod{4}$ период равен 4b, то есть $\left(\frac{a+4b}{b}\right)= \left(\frac{a}{b}\right)$

• Периодичность по переменной b: если $a\neq0$, то

• • при $a\equiv0; 1\mod{4}$ период равен |a|, то есть $\left(\frac{a}{b+\left|a\right |}\right)= \left(\frac{a}{b}\right)$

• • при $a\equiv2; 3\mod{4}$ период равен 4|a|, то есть $\left(\frac{a}{b+4\left|a\right |}\right)= \left(\frac{a}{b}\right)$

• Если b — нечётное натуральное число, то выполнены свойства символа Якоби:

• • $\left(\frac{1}{b}\right) = 1$

• • $\left(\frac{-1}{b}\right) = (-1)^{\frac{b-1}{2}}$

• • $\left(\frac{2}{b}\right) = (-1)^{\frac{b^2-1}{8}}$

• Аналог квадратичного закона взаимности: если A,B — нечётные натуральные числа, то $\left(\frac{A}{B}\right) \left(\frac{B}{A}\right) = (-1)^{\frac{A-1}{2}\cdot\frac{B-1}{2}}$.

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

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

 Если b = 0 то

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

  Если $|a|\neq1$, то выход из алгоритма с ответом 0

 Конец Если

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

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

 v = 0

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

  v: = v + 1;b: = b / 2

 Конец цикла

 Если v – чётное, то k=1, иначе иначе $k=(-1)^{\frac{a^2-1}{8}}$

 Если b < 0, то

  b: =  − b

  Если a < 0, то k: =  − k

 Конец Если

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

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

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

 Конец Если

 v: = 0

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

  v: = v + 1;a: = a / 2

 Конец цикла

 Если v – нечётное, то $k:=(-1)^{\frac{b^2-1}{8}}k$

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

 $k:=k(-1) ^{\frac{(a-1)(b-1)}{4}}$

 r: =  | a | 

 $a:=b\mod{r}$ (наименьший положительный вычет)

 b: = r

 Идти на шаг 3

Замечание: для подсчёта $(-1)^{\frac{a^2-1}{8}}$ не нужно вычислять показатель степени, достаточно знать остаток от деления a на 8. Это увеличивает скорость работы алгоритма.

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

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