Викия

Математика

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

1457статей на
этой вики
Добавить новую страницу
Обсуждение0 Share

Обнаружено использование расширения AdBlock.


Викия — это свободный ресурс, который существует и развивается за счёт рекламы. Для блокирующих рекламу пользователей мы предоставляем модифицированную версию сайта.

Викия не будет доступна для последующих модификаций. Если вы желаете продолжать работать со страницей, то, пожалуйста, отключите расширение для блокировки рекламы.

Файл:Leopold Kronecker.jpg
Не следует путать с термином «Дельта Кронекера».

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

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


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

Символ Кронекера-Якоби \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_1, ..., p_n — простые (не обязательно различные), то
\left(\frac{a}{b}\right) = \left(\frac{a}{p_1}\right)\cdot...\cdot\left(\frac{a}{p_n}\right),

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


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


    • В частности, \left(\frac{a^2b}{c}\right) =\left(\frac{b}{c}\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}}



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

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. Это увеличивает скорость работы алгоритма.

См. также Править

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

Викия-сеть

Случайная вики